Johnson graphs are panconnected

DOI10.1007/S12044-019-0527-3MaRDI QIDQ2274796zbMATH OpenOpenAlexWikidataFDO

Authors Akram Heidari, S. Morteza Mirafzal

Publication date 1 October 2019

Published in Proceedings of the Indian Academy of Sciences. Mathematical Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.07207

zbMATH Keywords

Johnson graphsquare of a graphpanconnected graph

Mathematics Subject Classification ID

Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Applications of graph theory to circuits and networks (94C15)

Abstract: For any given $n,minmathbbN$ with $m<n$, the Johnson graph $J(n,m)$ is defined as the graph whose vertex set is $V=vmidvsubseteq[n]=1,\mathrm{...},n,|v|=m$, where two vertices $v$,$w$ are adjacent if and only if $|vcapw|=m-1$. A graph $G$ of order $n>2$ is panconnected if for every two vertices $u$ and $v$, there is a $u$-$v$ path of length $l$ for every integer $l$ with $d(u,v)leqlleqn-1$. In this paper, we prove that the Johnson graph $J(n,m)$ is a panconnected graph.

Recommendations

• Johnson graphs are Hamilton-connected
• scientific article; zbMATH DE number 568844
• The super-connectivity of Johnson graphs
• scientific article; zbMATH DE number 679710
• Pancyclic and panconnected line graphs
• Pan-\(H\)-linked graphs
• Spectrum of Johnson graphs
• A new result about panconnectivity on graphs
• scientific article; zbMATH DE number 165078
• Panconnected index of graphs

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 5008491 (Why is no real title available?)
• scientific article; zbMATH DE number 894528 (Why is no real title available?)
• A new class of integral graphs constructed from the hypercube
• Bipartite Kneser graphs are Hamiltonian
• Connectivity of transitive graphs
• Graph theory
• In the square of graphs, Hamiltonicity and pancyclicity, Hamiltonian connectedness and panconnectedness are equivalent concepts
• Johnson graphs are Hamilton-connected
• Some algebraic properties of bipartite Kneser graphs.
• The automorphism group of the bipartite Kneser graph
• The square of a block is Hamiltonian connected

Cited in

(6)

• Cayley properties of the line graphs induced by consecutive layers of the hypercube
• On the automorphism groups of connected bipartite irreducible graphs
• Some algebraic properties of the subdivision graph of a graph
• The Johnson graphs satisfy a distance extension property
• \(L(n)\) graphs are vertex-pancyclic and Hamilton-connected
• Some remarks on the square graph of the hypercube

This page was built for publication: Johnson graphs are panconnected

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2274796)