Unified Spectral Hamiltonian Results of Balanced Bipartite Graphs and Complementary Graphs
- PDF / 498,450 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 44 Downloads / 201 Views
(0123456789().,-volV) (0123456789().,-volV)
ORIGINAL PAPER
Unified Spectral Hamiltonian Results of Balanced Bipartite Graphs and Complementary Graphs Muhuo Liu1 • Yang Wu2
•
Hong-Jian Lai3
Received: 11 February 2019 / Revised: 1 June 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract There have been researches on sufficient spectral conditions for Hamiltonian properties and path-coverable properties of graphs. Utilizing the Bondy–Chva´tal closure, we provide a unified approach to study sufficient graph eigenvalue conditions for these properties and sharpen several former spectral Hamiltonian results on balanced bipartite graphs and complementary graphs. Keywords Hamiltonian graphs Traceable graphs (Almost)balanced bipartite graphs complementary graphs (Signless Laplacian)spectral radius
Mathematics Subject Classification 05C50 15A18 15A36
1 Introduction We study simple undirected graphs, with undefined terms and notation following [3]. As in [3], dðGÞ, jðGÞ, j0 ðGÞ and G denote the minimum degree, the connectivity, the edge-connectivity and the complement of a graph G, respectively. For an integer k, a graph G is k-connected (resp. k-edge-connected) if jðGÞ k & Yang Wu [email protected] Muhuo Liu [email protected] Hong-Jian Lai [email protected] 1
Department of Mathematics, South China Agricultural University, Guangzhou, China
2
Faculty of Information Technology, Macau University of Science and Technology, Macau, China
3
Department of Mathematics, West Virginia University, Morgantown, WV, USA
123
Graphs and Combinatorics
(resp. j0 ðGÞ k). Throughout this paper, for an integer s 1, let sK1 be the edgeless graph with s vertices. Let S VðGÞ be a subset. For any vertex u 2 VðGÞ, define NS ðuÞ ¼ fv 2 S : uv 2 EðGÞg. If H is a subgraph of G, then we use NH ðuÞ for NVðHÞ ðuÞ. In particular, NG ðuÞ ¼ fv 2 VðGÞ : uv 2 EðGÞg and dG ðuÞ ¼ jNG ðuÞj. We often use N(u) and d(u) for NG ðuÞ and dG ðuÞ, respectively, when G is understood from the context. A graph G is nontrivial if it has at least one edge. As in [3], G is Hamiltonian (resp., traceable) if G contains a spanning cycle (resp., spanning path), and is Hamilton-connected if any pair of distinct vertices are joined by a spanning path. Definition 1.1 Let q 0 be an integers and let G be a graph. (i)
(ii) (iii)
G is q-traceable (resp. q-Hamiltonian, q-Hamilton-connected) if any removal of at most q vertices from G results in a traceable graph (resp., a Hamiltonian graph, a Hamilton-connected graph). G is q-edge-Hamiltonian if any collection of vertex-disjoint paths with at most q edges altogether must belong to a Hamiltonian cycle in G. G is q-path-coverable if V(G) can be covered by no more than q vertexdisjoint paths.
Following [3], we use G[X] to denote the subgraph of G induced by X. By Definition 1.1(i), a q-Hamiltonian graph is also a ðq þ 1Þ-traceable graph. However, a ðq þ 1Þ-traceable graph is not necessarily a q-Hamiltonian graph. For instance, the Petersen graph is 1-traceable, but not 0-Hamiltonian. Mo
Data Loading...
