Forbidden Subgraphs for a Graph to Have a Hamiltonian Path Square
- PDF / 370,002 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 72 Downloads / 189 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Forbidden Subgraphs for a Graph to Have a Hamiltonian Path Square Xiaojing Yang1,2 • Liming Xiong1 Received: 11 March 2019 / Revised: 11 April 2020 Springer Japan KK, part of Springer Nature 2020
Abstract The square of a graph is obtained by adding an edge between each pair of vertices that are of distance 2 in the original graph. If a graph G has a hamiltonian path (or cycle) square, then the square of the hamiltonian path (or cycle) is called a hamiltonian path (or cycle) square of G. Chen and Shan (Graphs Comb 31:2113–2124, 2015) characterized all forbidden pairs for a 4-connected graph to have a hamiltonian cycle square. In this paper, we completely characterize pairs of connected forbidden subgraphs for a k-connected (k 2 f1; 2; 3; 4g) graph with maximal degree at least 4 to have a hamiltonian path square. Note that the maximal degree condition is necessary for graphs of order at least 5 to have a hamiltonian path square. Keywords Square Forbidden subgraph Hamiltonian path
1 Introduction All graphs considered in this paper are finite, undirected and simple. For notation and terminology not defined here, see [1]. We denote by V(G), E(G), DðGÞ, dðGÞ, aðGÞ, jðGÞ, the vertex set, edge set, maximum degree, minimum degree, independent number, vertex connectivity of a graph G, respectively. We denote by NG ðvÞ (simply N(v)) and dG ðvÞ (simply d(v)) the neighborhood and the degree of a vertex v in G, respectively. Let NG ½v ¼ NG ðvÞ [ fvg. Let S VðGÞ and & Liming Xiong [email protected] Xiaojing Yang [email protected] 1
School of Mathematics and Statistics, Beijing Key Laboratory on MCAACI, Beijing Institute of Technology, Beijing 100081, People’s Republic of China
2
School of Mathematics and Satistics, Henan University, Kaifeng 475004, People’s Republic of China
123
Graphs and Combinatorics
S0 EðGÞ. The induced subgraph of G is denoted by G[S] or G½S0 . We use G½VðGÞnS or G½EðGÞnS0 to denote the subgraph G S or G S0 , respectively. If the number of components of G S is greater than the number of components of G, then S is a vertex-cut of G. We call the vertex in S a cut-vertex if jSj ¼ 1. A path with end-vertices u and v of G is denoted by PG ðu; vÞ. Let Pn and Cn denote the path and cycle of order n, respectively. Let Kn and Km;n denote the complete graph and complete bipartite graph, respectively. A clique is a complete subgraph of a graph. A hamiltonian path of a graph is a path containing all vertices of the graph. A graph is hamiltonian if it has a hamiltonian cycle, i.e., a cycle containing all vertices of the graph. The square of a graph G is obtained by adding an edge between each pair of vertices that are of distance 2 in G, denoted as G2 . Suppose that Pn (or Cn ) is a hamiltonian path (or cycle) of a graph G. If P2n G (or Cn2 G), then P2n (or Cn2 ) is called a hamiltonian path (or cycle) square of G. The earliest problem on hamiltonian cycle square can be traced back to a conjecture proposed by Po´sa (see Er
Data Loading...
