Search

For a 2-connected graph G , the relative length of G , denoted by diff (G) , is the difference between the orders of a longest path and a longest cycle in G. This parameter is used as a measure to estimate how close a given graph is to a hamiltonian graph. Let σ k (G) be the least value of the sums of degrees of vertices in independent sets of cardinality k. In 2008, Paulusma and Yoshimoto proved that a 2-connected triangle-free graph G of order n with σ 4 (G) ≥ n + 2 satisfies diff (G) ≤ 1 unless G is isomorphic to one exceptional graph G 0. In this paper, we extend their result and prove that for an integer s with 2 3 (n + 4) < s ≤ n + 2 , a 2-connected triangle-free graph of order n with σ 4 (G) ≥ s satisfies diff (G) ≤ n + 3 − s unless s = σ 4 (G) = n + 2 and G = G 0. [ABSTRACT FROM AUTHOR]

A connected graph G with at least 2 m + 2 n + 2 vertices is said to satisfy the property E ( m , n ) if G contains a perfect matching and for any two sets of independent edges M and N with | M | = m and | N | = n with M ∩ N = ∅ , there is a perfect matching F in G such that M ⊂ F and N ∩ F = ∅ . In particular, if G is E ( m , 0 ) , we say that G is m -extendable. One of the authors has proved that every m -tough graph of even order at least 2 m + 2 is m -extendable (Plummer, 1988). Chen (1995) and Robertshaw and Woodall (2002) gave sufficient conditions on binding number for m -extendability. In this paper, we extend these results and give lower bounds on toughness and binding number which guarantee E ( m , n ) . [ABSTRACT FROM AUTHOR]

A classical result of Ore states that if a graph G of order n satisfies deg G x + deg G y ≥ n − 1 for every pair of nonadjacent vertices x and y of G , then G contains a hamiltonian path. In this note, we interpret a hamiltonian path as a spanning tree which is a subdivision of K 2 and extend Ore’s result to a sufficient condition for the existence of a spanning tree which is a subdivision of a tree of a bounded order. We prove that for a positive integer k , if a connected graph G satisfies deg G x + deg G y ≥ n − k for every pair of nonadjacent vertices x and y of G , then G contains a spanning tree which is a subdivision of a tree of order at most k + 2 . We also discuss the sharpness of the result. [ABSTRACT FROM AUTHOR]

Abstract: Let denote the independence number of graph , i.e., the size of any maximum independent set of vertices. A graph is contraction-critical (with respect to ) if , for every edge , where denotes the graph obtained from by shrinking the edge to a single vertex and deleting the loop thus formed. Let us denote the class of all such contraction-critical graphs by . First it is shown that all graphs in must be bipartite. Let be a bipartite graph with bipartition . It is then shown that (a) if , then if and only if is the unique maximum independent set in if and only if is 1-expanding, while (b) if , then if and only if and are the only two maximum independent sets in if and only if is 1-extendable. It follows that graphs can be recognized in polynomial time. [Copyright &y& Elsevier]

Abstract: For a set of connected graphs, a spanning subgraph of a graph is an -factor if every component of is isomorphic to some member of . Amahashi and Kano [A. Amahashi, M. Kano, On factors with given components, Discrete Math. 42 (1982) 1–6] proved that a graph satisfying for every has a -factor, where is the number of isolated vertices in and denotes the star with edges. Here we exclude small stars from the set and prove that a graph satisfying for every has a -factor. [Copyright &y& Elsevier]

Abstract: We consider 2-factors with a bounded number of components in the -times iterated line graph . We first give a characterization of graph such that has a 2-factor containing at most components, based on the existence of a certain type of subgraph in . This generalizes the main result of [L. Xiong, Z. Liu, Hamiltonian iterated line graphs, Discrete Math. 256 (2002) 407–422]. We use this result to show that the minimum number of components of 2-factors in the iterated line graphs is stable under the closure operation on a claw-free graph . This extends results in [Z. Ryjáček, On a closure concept in claw-free graphs, J. Combin. Theory Ser. B 70 (1997) 217–224; Z. Ryjáček, A. Saito, R.H. Schelp, Closure, 2-factors and cycle coverings in claw-free graphs, J. Graph Theory 32 (1999) 109–117; L. Xiong, Z. Ryjáček, H.J. Broersma, On stability of the hamiltonian index under contractions and closures, J. Graph Theory 49 (2005) 104–115]. [Copyright &y& Elsevier]

Abstract: A set S of vertices in a graph G is said to be an edge-dominating set if every edge in G is incident with a vertex in S. A cycle in G is said to be a dominating cycle if its vertex set is an edge-dominating set. Nash-Williams [Edge-disjoint hamiltonian circuits in graphs with vertices of large valency, Studies in Pure Mathematics, Academic Press, London, 1971, pp. 157–183] has proved that every longest cycle in a 2-connected graph of order n and minimum degree at least is a dominating cycle. In this paper, we prove that for a prescribed positive integer k, under the same minimum degree condition, if n is sufficiently large and if we take k disjoint cycles so that they contain as many vertices as possible, then these cycles form an edge-dominating set. Nash-Williams’ Theorem corresponds to the case of of this result. [Copyright &y& Elsevier]

Abstract: For a pair of vertices x and y in a graph G, we denote by the distance between x and y in G. We call x a boundary vertex of y if x and y belong to the same component and for each neighbor of x in G. A boundary vertex of some vertex is simply called a boundary vertex, and the set of boundary vertices in G is called the boundary of G, and is denoted by . In this paper, we investigate graphs with a small boundary. Since a pair of farthest vertices are boundary vertices, for every connected graph G of order at least two. We characterize the graphs with boundary of order at most three. We cannot give a characterization of graphs with exactly four boundary vertices, but we prove that such graphs have minimum degree at most six. Finally, we give an upper bound to the minimum degree of a connected graph G in terms of . [Copyright &y& Elsevier]

Abstract: Let G be a balanced bipartite graph with partite sets X and Y, which has a perfect matching, and let and . Let k be a positive integer. Then we prove that if G has k internally disjoint alternating paths between x and y with respect to some perfect matching, then G has k internally disjoint alternating paths between x and y with respect to every perfect matching. [Copyright &y& Elsevier]

Let G be a graph and let f be a non-negative integer-valued function defined on V(G). Then a cycle C is called an f-dominating cycle if dG(v,C)⩽f(v) holds for each v∈V(G), where dG(v,C) denotes the distance between v and C. A set S is called an f-stable set if dG(u,v)⩾f(u)+f(v) holds for each pair of distinct vertices u, v in S, and denote by αf(G) the order of a largest f-stable set in G. In this paper, we prove that if a k-connected graph G (k⩾2) satisfies αf+1(G)⩽k, then G has an f-dominating cycle, where f+1 is the function defined by (f+1)(v)=f(v)+1. By taking an appropriate function as f, we can deduce a number of known results from this theorem. [Copyright &y& Elsevier]

A graph G is said to be n-factor-critical if G−T has a perfect matching for every T⊂V(G) with |T|=n. For a vertex x of a graph G, local completion of G at x is the operation of joining every pair of nonadjacent vertices in NG(x). For a property P of graphs, a vertex x in a graph G is said to be P-eligible if the subgraph of G induced by NG(x) satisfies P but it is not complete. For a graph G, a graph H is said to be a P-closure of G if there exists a series of graphs G=G0,G1,…,Gr=H such that Gi is obtained from Gi−1 by local completion at some P-eligible vertex in Gi−1 and H=Gr has no P-eligible vertex. In this paper, we investigate the relation between factor-criticality and a P-closure, where P is a bounded independence number or a bounded domination number. [Copyright &y& Elsevier]

Let G=(X,Y) be a 2-connected balanced bipartite graph with |X|=|Y|=n. In this paper, we prove that if |N(x1)∪N(x2)|+|N(y1)∪N(y2)|⩾n+2 for any {x1,x2}⊆X and {y1,y2}⊆Y, then G is hamiltonian except when G is a special graph on 8 or on 12 vertices. [Copyright &y& Elsevier]

An orientation of a graph is semi-transitive if it is acyclic, and for any directed path v 0 → v 1 → ⋯ → v k either there is no edge between v 0 and v k , or v i → v j is an edge for all 0 ≤ i < j ≤ k. An undirected graph is semi-transitive if it admits a semi-transitive orientation. Semi-transitive graphs include several important classes of graphs such as 3-colourable graphs, comparability graphs, and circle graphs, and they are precisely the class of word-representable graphs studied extensively in the literature. In this paper, we study semi-transitive orientability of the celebrated Kneser graph K (n , k) , which is the graph whose vertices correspond to the k -element subsets of a set of n elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. We show that K (n , k) is not semi-transitive for any even integers k ≥ 2 and n ≥ 3 k and for any odd integers k ≥ 3 and n ≥ 3 k + 3. On the other hand, for m ∈ { 2 k , 2 k + 1 } , K (n , k) is semi-transitive. Also, if K (p , q) is not semi-transitive, then K (n , k) is not semi-transitive for any k ≥ q and n ≥ k q p. Moreover, we show computationally that K (8 , 3) is not semi-transitive, which results in K (n , k) being not semi-transitive for any k ≥ 3 and n ≥ 8 ⋅ k 3 . A certain subgraph S of K (8 , 3) presented by us and K (8 , 3) itself are the first explicit examples of triangle-free non-semi-transitive graphs, whose existence was established via Erdős' theorem by Halldórsson, Kitaev and Pyatkin in Halldórsson et al. (2011). Finally, the complement graph K (n , k) ¯ of K (n , k) is not semi-transitive if and only if n > 2 k. [ABSTRACT FROM AUTHOR]

A matching M in a graph G is said to be extendable if there exists a perfect matching of G containing M . In 1989, it was shown that every connected planar graph with at least 8 vertices has a matching of size three which is not extendable. In contrast, the study of extending certain matchings of size three or more has made progress in the past decade when the given graph is 5 -connected planar triangulation or 5 -connected plane graphs with few non-triangular faces. In this paper, we prove that if G is a 5 -connected plane graph of even order in which at most two faces are not triangular and M is a matching of size four in which the edges lie pairwise distance at least three apart, then M is extendable. A related result concerning perfect matching with proscribed edges is shown as well. [ABSTRACT FROM AUTHOR]

Abstract: For a set of connected graphs, a graph is said to be -free if does not contain any member of as an induced subgraph. The members of are referred to as forbidden subgraphs. When we study the relationship between forbidden subgraphs and a certain graph property, we often allow the possibility of the existence of exceptional graphs as long as their number is finite. However, in this type of research, if the set of -connected -free graphs itself, denoted by , is finite, then every graph in logically satisfies all the graph properties, except for possibly a finite number of exceptions. If this occurs, does not give any information about a particular property. We think that such sets obscure the view in the study of forbidden subgraphs, and we want to remove them. With this motivation, we study the sets with finite . We prove that if and is finite, then either or consists of a complete graph and a star. For each of the values of , , we then characterize all the pairs such that is finite. We also give a complete characterization of with and finite . [Copyright &y& Elsevier]

Abstract: Let be a graph of order . An even squared Hamiltonian cycle (ESHC) of is a Hamiltonian cycle of with chords for all (where for ). When is even, an ESHC contains all bipartite -regular graphs of order . We prove that there is a positive integer such that for every graph of even order , if the minimum degree is , then contains an ESHC. We show that the condition of being even cannot be dropped and the constant cannot be replaced by . Our results can be easily extended to even th powered Hamiltonian cycles for all . [Copyright &y& Elsevier]

Abstract: In 1960 Ore proved the following theorem: Let G be a graph of order n. If for every pair of nonadjacent vertices u and , then G is hamiltonian. In this note we strengthen Ore''s theorem as follows: we determine the maximum number of pairs of nonadjacent vertices that can have degree sum less than n (i.e. violate Ore''s condition) but still imply that the graph is hamiltonian. Some other sufficient conditions (i.e. Fan''s condition) for hamiltonian graphs are strengthened as well. [Copyright &y& Elsevier]

A graph G is said to be equimatchable if every matching in G extends to (i.e., is a subset of) a maximum matching. In this paper, we use the Gallai–Edmonds decomposition theory for matchings to determine the equimatchable members of two important graph classes. We find that there are precisely 23 3-connected planar graphs (i.e., 3-polytopes) which are equimatchable and that there are only two cubic equimatchable graphs. [Copyright &y& Elsevier]

A cycle of order k is called a k -cycle. A non-induced cycle is called a chorded cycle. Let n be an integer with n ≥ 4 . Then a graph G of order n is chorded pancyclic if G contains a chorded k -cycle for every integer k with 4 ≤ k ≤ n . Cream, Gould and Hirohata (Australas. J. Combin. 67 (2017), 463–469) proved that a graph of order n satisfying deg G u + deg G v ≥ n for every pair of nonadjacent vertices u , v in G is chorded pancyclic unless G is either K n 2 , n 2 or K 3 □ K 2 , the Cartesian product of K 3 and K 2 . They also conjectured that if G is Hamiltonian, we can replace the degree sum condition with the weaker density condition | E ( G ) | ≥ 1 4 n 2 and still guarantee the same conclusion. In this paper, we prove this conjecture by showing that if a graph G of order n with | E ( G ) | ≥ 1 4 n 2 contains a k -cycle, then G contains a chorded k -cycle, unless k = 4 and G is either K n 2 , n 2 or K 3 □ K 2 , Then observing that K n 2 , n 2 and K 3 □ K 2 are exceptions only for k = 4 , we further relax the density condition for sufficiently large k . [ABSTRACT FROM AUTHOR]

Aldred and Plummer (1999) have proved that every m -connected K 1 , m − k + 2 -free graph of even order contains a perfect matching which avoids k prescribed edges. They have also proved that the result is best possible in the range 1 ≤ k ≤ 1 2 ( m + 1 ) . In this paper, we show that if 1 2 ( m + 2 ) ≤ k ≤ m − 1 , their result is not best possible. We prove that if m ≥ 4 and 1 2 ( m + 2 ) ≤ k ≤ m − 1 , every K 1 , ⌈ 2 m − k + 4 3 ⌉ -free graph of even order contains a perfect matching which avoids k prescribed edges. While this is a best possible result in terms of the order of a forbidden star, if 2 m − k + 4 ≡ 0 ( mod 3 ) , we also prove that only finitely many sharpness examples exist. [ABSTRACT FROM AUTHOR]

Abstract: For an integer with and a pair of connected graphs and of order at least three, we say that is a -forbidden pair if every -connected -free graph, except possibly for a finite number of exceptions, is Hamiltonian. If no exception arises, is said to be a strong -forbidden pair. The 2-forbidden pairs and the strong 2-forbidden pairs are determined by Faudree and Gould (1997) and Bedrossian (1991) , respectively. All of them contain . In this paper, we prove that is a strong -forbidden pair, which shows that is not always necessary in a -forbidden pair for . On the other hand, we prove that each -forbidden pair contains for some . We also discuss several other Hamiltonian properties of -connected -free graphs. [Copyright &y& Elsevier]

Abstract: In this note, we consider a minimum degree condition for a hamiltonian graph to have a 2-factor with two components. Let G be a graph of order . Dirac''s theorem says that if the minimum degree of G is at least , then G has a hamiltonian cycle. Furthermore, Brandt et al. [J. Graph Theory 24 (1997) 165–173] proved that if , then G has a 2-factor with two components. Both theorems are sharp and there are infinitely many graphs G of odd order and minimum degree which have no 2-factor. However, if hamiltonicity is assumed, we can relax the minimum degree condition for the existence of a 2-factor with two components. We prove in this note that a hamiltonian graph of order and minimum degree at least has a 2-factor with two components. [Copyright &y& Elsevier]

Abstract: In this paper we generalize a Theorem of Jung which shows that 1-tough graphs with are hamiltonian. Our generalization shows that these graphs contain a wide variety of 2-factors. In fact, these graphs contain not only 2-factors having just one cycle (the hamiltonian case) but 2-factors with cycles, for any such that . [Copyright &y& Elsevier]

Let G be a bipartite graph with bipartition (X,Y) which has a perfect matching. It is proved that G is n-extendable if and only if for any perfect matching M of G and for each pair of vertices x in X and y in Y there are n internally disjoint M-alternating paths connecting x and y. Furthermore, these n paths start and end with edges in E(G)&z.drule;M. This theorem is then generalized. [Copyright &y& Elsevier]

In this paper, we consider 2-connected multigraphs in which every cycle has length congruent to a modulo b (b&ges;2). We prove that there exists such a multigraph which is homomorphic to a graph with minimum degree at least three only if a=0, and that there exists such a graph only if a=0 and b=2. We also study the distribution of paths whose internal vertices have degree exactly two, and show a relation between these paths and edges in a 2-connected graph whose deletion results in a 2-connected graph. [Copyright &y& Elsevier]

An edge-colored graph G is rainbow if each edge receives a different color. For a connected graph H , G is rainbow H -free if G does not contain a rainbow subgraph which is isomorphic to H. By definition, if H ′ is a connected subgraph of H , every rainbow H ′ -free graph is rainbow H -free. In this note, we consider a kind of reverse implication, where H ′ is a connected proper supergraph and every rainbow H ′ -free graph edge-colored in sufficiently many colors is rainbow H -free. We determine when this implication occurs. [ABSTRACT FROM AUTHOR]

The classical Ore's Theorem states that every graph G of order n ≥ 3 with σ 2 (G) ≥ n is hamiltonian, where σ 2 (G) = min { d G (x) + d G (y) : x , y ∈ V (G) , x ≠ y , x y ∉ E (G) }. Recently, Ferrara, Jacobson and Powell (Discrete Math. 312 (2012), 459–461) extended the Moon–Moser Theorem and characterized the non-hamiltonian balanced bipartite graphs H of order 2 n ≥ 4 with partite sets X and Y satisfying σ 1 , 1 (H) ≥ n , where σ 1 , 1 (H) = min { d H (x) + d H (y) : x ∈ X , y ∈ Y , x y ∉ E (H) }. Though the latter result apparently deals with a narrower class of graphs, we prove in this paper that it implies Ore's Theorem for graphs of even order. [ABSTRACT FROM AUTHOR]