Search

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: In this paper, we consider coloring of graphs under the assumption that some vertices are already colored. Let be an -colorable graph and let . Albertson (1998) has proved that if every pair of vertices in has distance at least four, then every -coloring of can be extended to an -coloring of , where is the subgraph of induced by . In this paper, we allow to have pairs of vertices of distance at most three, and investigate how the number of such pairs affects the number of colors we need to extend the coloring of . We also study the effect of pairs of vertices of distance at most two, and extend the result by Albertson and Moore (1999). [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: Given a claw-free graph and two non-adjacent vertices x and y without common neighbours we prove that there exists a hole through x and y unless the graph contains the obvious obstruction, namely a clique separating x and y. We derive two applications: We give a necessary and sufficient condition for the existence of an induced x–z path through y, where are prescribed vertices in a claw-free graph; and we prove an induced version of Mengerʼs theorem between four terminal vertices. Finally, we improve the running time for detecting a hole through x and y and for the Three-in-a-Tree problem, if the input graph is claw-free. [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: 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]

We give a reduction theorem for 3-connected graphs of minimum degree at least four. Let $${\mathcal{P}}_{3,4}$$ be the class of 3-connected graphs of minimum degree at least four. For a vertex x of degree four in G, splitting at x is an operation of adding at most two independent edges connecting some of the neighbors of x and deleting x. A set of five vertices C = { a, b, x, y, z} in G is said to be a crown if N G ( a) = { b, x, y, z} and N G ( b) = { a, x, y, z}. Given a crown C in G, reduction of C is the operation of deleting { a, b} and adding all the missing edges among { x, y, z}. In this paper, we prove that for every vertex x in a graph $$G\in{\mathcal{P}}_{3,4}$$ , there exists either (1) an edge e such that its contraction yields a graph in $${\mathcal{P}}_{3,4}$$ and at least one of its endvertices is of distance at most two from x, (2) a vertex v of degree four such that v is of distance at most two from x and some splitting at v yields a graph in $${\mathcal{P}}_{3,4}$$ , or (3) a crown C containing x whose reduction yields a graph in $${\mathcal{P}}_{3,4}$$ . [ABSTRACT FROM AUTHOR]

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]

Let G be a graph and let x be a vertex of degree four with NG(x)={a,b,c,d}. Then the operation of deleting x and adding the edges ab and cd is called splitting at x. An edge e of a graph G is said to be k-contractible if contraction of e yields a k-connected graph. Splitting has been studied as a reduction method to preserve edge-connectivity. In this paper, we consider splitting and 4-contractible edges as tools for reduction of 4-connected graphs. We prove that for a 4-connected graph G of order at least six, there exists either a 4-contractible edge or a vertex eligible for splitting preserving 4-connectedness near every vertex in G. [Copyright &y& Elsevier]

Let H be a set of connected graphs, each of which has order at least three, and suppose that there exist infinitely many connected H‐free graphs of minimum degree at least  two and all except for finitely many of them have a 2‐factor. In [J. Graph Theory, 64 (2010), 250–266], we proved that if |H|≤3, then one of the members in H is a star. In this article, we determine the remaining members of H and hence give a complete characterization of the pairs and triples of forbidden subgraphs. [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]

A graph is called $$2K_2$$ -free if it does not contain two independent edges as an induced subgraph. Gao and Pasechnik conjectured that every $$\frac{3}{2}$$ -tough $$2K_2$$ -free graph with at least three vertices has a spanning trail with maximum degree at most 4. In this paper, we confirm this conjecture. We also provide examples for all $$t < \frac{5}{4}$$ of t-tough graphs that do not have a spanning trail with maximum degree at most 4. [ABSTRACT FROM AUTHOR]

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: We extend the notion of a defensive alliance to weighted graphs. Let be a weighted graph, where is a graph and be a function from to the set of positive real numbers. A non-empty set of vertices in is said to be a weighted defensive alliance if holds for every vertex in . Fricke et al. (2003) have proved that every graph of order has a defensive alliance of order at most . In this note, we generalize this result to weighted defensive alliances. Let be a graph of order . Then we prove that for any weight function on , has a defensive weighted alliance of order at most . We also extend the notion of strong defensive alliance to weighted graphs and generalize a result in Fricke et al. (2003) . [ABSTRACT FROM AUTHOR]

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 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]

This issue is dedicated in honor of Professors Eiichi Bannai and Hikoe Enomoto on the occasion of their 75th birthdays. Graph Bannai and Enomoto are leading pioneers of combinatorics in Japan. [Extracted from the article]

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]

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]