Search

A cyclic $$(n_{3})$$ configuration is a combinatorial configuration whose automorphism group contains a cyclic permutation of the points of the configuration; that is, the points of the configuration may be considered to be elements of $${\mathbb {Z}}_{n}$$ , and the lines of the configuration as cyclic shifts of a single fixed starting block [0, a, b], where $$a, b \in {\mathbb {Z}}_{n}$$ . We denote such configurations as $$\mathrm{Cyc}_{n}(0,a,b)$$ . One of the fundamental questions in the study of configurations is that of geometric realizability. In the case where $$n = 2m$$ , it is combinatorially possible to divide the points and lines of the configuration into two classes according to parity, so it is natural to ask whether the configuration can be realized using those classes. We provide methods for producing geometric realizations of configurations $$\mathrm{Cyc}_{2m}(0,a,b)$$ that have two symmetry classes under the maximal rotational subgroup of the geometric symmetry group (that is, chiral astral realizations), and we provide a number of constraints on a and b that guarantee such a realization exists. Experiments on up to 500 points suggest that, with the exception of some small sporadic examples and a single infinite family $$\mathrm{Cyc}_{2(k+1)}(0,1,k)$$ , $$k \ge 3$$ and k odd, all cyclic $$(2m_{3})$$ configurations are realizable as geometric chiral astral configurations using the methods described in this paper.

An edge-colored graph is properly connected if for every pair of vertices u and v there exists a properly colored uv-path (i.e. a uv-path in which no two consecutive edges have the same color). The proper connection number of a connected graph G, denoted pc(G), is the smallest number of colors needed to color the edges of G such that the resulting colored graph is properly connected. An edge-colored graph is flexibly connected if for every pair of vertices u and v there exist two properly colored paths between them, say P and Q, such that the first edges of P and Q have different colors and the last edges of P and Q have different colors. The flexible connection number of a connected graph G, denoted fpc(G), is the smallest number of colors needed to color the edges of G such that the resulting colored graph is flexibly connected. In this paper, we demonstrate several methods for constructing graphs with pc(G) = 2 and fpc(G) = 2. We describe several families of graphs such that pc(G) ≥ 2 and we settle a conjecture from [BFG+12]. We prove that if G is connected and bipartite, then pc(G) = 2 is equivalent to being 2-edge-connected and fpc(G) = 2 is equivalent to the existence of a path through all cut-edges. Finally, it is proved that every connected, k-regular, Class 1 graph has flexible connection number 2.

Let G be a simple m × n bipartite graph with m ≥ n . We prove that if the minimum degree of G satisfies δ ( G ) ≥ m ∕ 2 + 1 , then G is bipanconnected: for every pair of vertices x , y , and for every appropriate integer 2 ≤ l ≤ 2 n , there is an x , y -path of length l in G .

A chord is an edge between two vertices of a cycle that is not an edge on the cycle. If a cycle has at least one chord, then the cycle is called a chorded cycle, and if a cycle has at least two chords, then the cycle is called a doubly chorded cycle. The minimum degree and the minimum degree-sum conditions are given for a graph to contain vertex-disjoint chorded (doubly chorded) cycles containing specified elements of the graph, i.e., specified vertices, specified edges as cycle-edges, specified paths, or specified edges as chords. Furthermore, the minimum degree condition is given for a graph to be partitioned into chorded cycles containing specified edges as cycle-edges.

A dominating path in a graph is a path P such that every vertex outside P has a neighbor on P. A result of Broersma from 1988 implies that if G is an n-vertex k-connected graph and , then G contains a dominating path. We prove the following results. The lengths of dominating paths include all values from the shortest up to at least . For , where a is a constant greater than 1/3, the minimum length of a dominating path is at most logarithmic in n when n is sufficiently large (the base of the logarithm depends on a). The preceding results are sharp. For constant s and , an s-vertex dominating path is guaranteed by when n is sufficiently large, but (where ) does not even guarantee a dominating set of size s. We also obtain minimum-degree conditions for the existence of a spanning tree obtained from a dominating path by giving the same number of leaf neighbors to each vertex.

A geometric 4-configuration is a collection of points and straight lines with the property that every point lies on exactly four lines in the collection and every line passes through exactly four points in the collection. This paper describes a method for constructing a large number of new infinite families of rotationally symmetric geometric 4-configurations which are movable; that is, there is at least one continuous parameter which preserves the symmetry of the configuration. In fact, the configurations in this paper have 2q continuous parameters for any integer $$q \ge 2$$q?2; previously the known classes of movable 4-configurations had only one or two degrees of freedom. The construction is extended to produce movable 4-configurations with dihedral symmetry. The paper ends with a number of open questions.

Let G be a simple $$m\times m$$m×m bipartite graph with minimum degree $$\delta (G)\ge m/2+1$$?(G)?m/2+1. We prove that for every pair of vertices x, y, there is a Hamiltonian cycle in G such that the distance between x and y along that cycle equals k, where $$2\le k

Let H be a graph. A graph G is uniquely H-saturated if G contains no subgraph isomorphic to H, but for every edge e in the complement of G (i.e., for each "nonedge" of G), $$G+e$$G+e contains exactly one subgraph isomorphic to H. The double star$$D_{s,t}$$Ds,t is the graph formed by beginning with $$K_2$$K2 and adding $$s+t$$s+t new vertices, making s of these adjacent to one endpoint of the $$K_2$$K2 and the other t adjacent to the other endpoint; $$D_{s,s}$$Ds,s is a balanced double star. Our main result is that the trees T for which there exist an infinite number of uniquely T-saturated graphs are precisely the balanced double stars. In addition we completely characterize uniquely tree-saturated graphs in the case where the tree is a star $$K_{1,t} = D_{0, t-1}$$K1,t=D0,t-1. We show that if T is a double star, then there exists a nontrivial uniquely T-saturated graph. We conjecture that the converse holds; we verify this conjecture for all trees of order at most 6. We conclude by giving some open problems.

Let X, Y be connected graphs. A graph G is -free if G contains a copy of neither X nor Y as an induced subgraph. Pairs of connected graphs such that every 3-connected -free graph is Hamilton connected have been investigated most recently in (Guantao Chen and Ronald J. Gould, Bull. Inst. Combin. Appl., 29 (2000), 25–32.) [8] and (H. Broersma, R. J. Faudree, A. Huck, H. Trommel, and H. J. Veldman, J. Graph Theory, 40(2) (2002), 104–119.) [5]. This paper improves those results. Specifically, it is shown that every 3-connected -free graph is Hamilton connected for and or N1, 2, 2 and the proof of this result uses a new closure technique developed by the third and fourth authors. A discussion of restrictions on the nature of the graph Y is also included.

For a fixed graph F , a graph G is F -saturated if there is no copy of F in G , but for any edge e ? G , there is a copy of F in G + e . The minimum number of edges in an F -saturated graph of order n will be denoted by sat ( n , F ) . A graph G is weakly F -saturated if G contains no copy of F and there is an ordering of the missing edges of G so that if they are added one at a time, each edge added creates a new copy of F . The minimum size of a weakly F -saturated graph G of order n will be denoted by wsat ( n , F ) . The graphs of order n that are weakly F -saturated will be denoted by wSAT ( n , F ) , and those graphs in wSAT ( n , F ) with wsat ( n , F ) edges will be denoted by wSAT ? ( n , F ) . The precise value of wsat ( n , F ) for many families of vertex disjoint copies of connected graphs such as small order graphs, trees, cycles, and complete graphs will be determined.

The connected forbidden subgraphs and pairs of connected forbidden subgraphs that imply a 2-connected graph is hamiltonian have been characterized by Bedrossian [Forbidden subgraph and minimum degree conditions for hamiltonicity, Ph.D. Thesis, Memphis State University, 1991], and extensions of these excluding graphs for general graphs of order at least 10 were proved by Faudree and Gould [Characterizing forbidden pairs for Hamiltonian properties, Discrete Math. 173 (1997) 45–60]. In this paper a complete characterization of connected forbidden subgraphs and pairs of connected forbidden subgraphs that imply a 2-connected graph of order at least 10 has a 2-factor will be proved. In particular it will be shown that the characterization for 2-factors is very similar to that for hamiltonian cycles, except there are seven additional pairs. In the case of graphs of all possible orders, there are four additional forbidden pairs not in the hamiltonian characterization, but a claw is part of each pair.

Given k ≥ 2 fixed positive integers p 1 , p 2 , … , p k − 1 ≥ 2 , and k vertices { x 1 , x 2 , … , x k } , let G be a simple graph of sufficiently large order n . It is proved that if δ ( G ) ≥ ( n + 2 k − 2 ) / 2 , then there is a Hamiltonian cycle C of G containing the vertices in order such that the distance along C is d C ( x i , x i + 1 ) = p i for 1 ≤ i ≤ k − 1 . Also, let { ( x i , y i ) | 1 ≤ i ≤ k } be a set of k disjoint pairs of vertices and a graph of sufficiently large graph n and p 1 , p 2 , … , p k ≥ 2 for k ≥ 2 fixed positive integers. It will be proved that if δ ( G ) ≥ ( n + 3 k − 1 ) / 2 , then there are k vertex disjoint paths P i ( x i , y i ) of length p i for 1 ≤ i ≤ k .

For a fixed graph F, a graph G is F-saturated if there is no copy of F in G, but for any edge e ∉ G, there is a copy of F in G + e. The minimum number of edges in an F-saturated graph of order n will be denoted by sat(n, F). A graph G is weakly F-saturated if there is an ordering of the missing edges of G so that if they are added one at a time, each edge added creates a new copy of F. The minimum size of a weakly F-saturated graph G of order n will be denoted by wsat(n, F). The graphs of order n that are weakly F-saturated will be denoted by wSAT(n, F), and those graphs in wSAT(n, F) with wsat(n, F) edges will be denoted by wSAT(n, F). The precise value of wsat(n, T) for many families of sparse graphs, and in particular for many trees, will be determined. More specifically, families of trees for which wsat(n, T) = |T|−2 will be determined. The maximum and minimum values of wsat(n, T) for the class of all trees will be given. Some properties of wsat(n, T) and wSAT(n, T) for trees will be discussed. Keywords: saturated graphs, sparse graphs, weak saturation.

Given a fixed positive integer k ≥ 2, let G be a simple graph of order n ≥ 6k. It is proved that if the minimum degree of G is at least n/2 + 1, then for every pair of vertices x and y, there exists a Hamiltonian cycle such that the distance between x and y along that cycle is precisely k.

A geometric $$k$$ -configuration is a collection of points and straight lines in the plane so that $$k$$ points lie on each line and $$k$$ lines pass through this point. We introduce a new construction method for constructing $$k$$ -configurations with non-trivial dihedral or chiral (i.e., purely rotational) symmetry, for any $$k \ge 3$$ ; the configurations produced have $$2^{k-2}$$ symmetry classes of points and lines. The construction method produces the only known infinite class of symmetric geometric 7-configurations, the second known infinite class of symmetric geometric 6-configurations, and the only known 6-configurations with chiral symmetry.

Given a fixed positive integer k2 and a fixed pair of sets of vertices X={x1,x2,,xk} and Y={y1,y2,,yk} in a graph G of sufficiently large order n, the sharp minimum degree condition (G)(n+k1)/2 will be shown to imply the existence of a Hamiltonian cycle C such that all of the vertices of X precede the vertices of Y for appropriate initial vertex and orientation of the cycle C. Also, a minimum degree condition along with a connectivity condition will be shown to imply the existence of a Hamiltonian cycle C such that the vertices of X and Y alternate on the cycle C.

Given a fixed positive integer k ≥ 2 and a fixed pair of vertices x and y in a graph of sufficiently large order n = n ( k ) , minimum degree conditions that imply the existence of a Hamiltonian cycle C such that the distance on the cycle C between x and y is precisely k will be proved.

An upper bound on the saturation number for graphs as well as associated extremal graphs was given by (Kaszonyi and Tuza in J. Graph Theory, 10:203---210, 1986). A minor improvement of that result, which was implied in their paper, will be stated. Using this result, a series of exact saturation numbers and associated extremal graphs will be proved for the nearly complete graphs K t ? E(L), where L is a graph of order at most 4.

Let G be a graph of order n and 3≤t≤n/4 be an integer. Recently, Kaneko and Yoshimoto [J Combin Theory Ser B 81(1) (2001), 100–109] provided a sharp δ(G) condition such that for any set X of t vertices, G contains a hamiltonian cycle H so that the distance along H between any two vertices of X is at least n/2t. In this article, minimum degree and connectivity conditions are determined such that for any graph G of sufficiently large order n and for any set of t vertices X⊆V(G), there is a hamiltonian cycle H so that the distance along H between any two consecutive vertices of X is approximately n/t. Furthermore, the minimum degree threshold is determined for the existence of a hamiltonian cycle H such that the vertices of X appear in a prescribed order at approximately predetermined distances along H. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 28–45, 2012

In this article, we prove that a line graph with minimum degree δ≥7 has a spanning subgraph in which every component is a clique of order at least three. This implies that if G is a line graph with δ≥7, then for any independent set S there is a 2-factor of G such that each cycle contains at most one vertex of S. This supports the conjecture that δ≥5 is sufficient to imply the existence of such a 2-factor in the larger class of claw-free graphs. It is also shown that if G is a claw-free graph of order n and independence number α with δ≥2n/α−2 and n≥3α3/2, then for any maximum independent set S, G has a 2-factor with α cycles such that each cycle contains one vertex of S. This is in support of a conjecture that δ≥n/α≥5 is sufficient to imply the existence of a 2-factor with α cycles, each containing one vertex of a maximum independent set. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 251–263, 2012, © 2012 Wiley Periodicals, Inc. (Kenta Ozeki is a Research Fellow of the Japan Society for the Promotion of Science.)

The path spectrum of a graph is the set of lengths of all maximal paths in the graph. A set S of positive integers is spectral if it is the path spectrum of a tree. We characterize the spectral sets containing at most two odd integers (and arbitrarily many even ones) and obtain several necessary conditions for a set to be spectral. We show that for each even integer s≥2 at least 1/4 of all subsets of the set {2,3,…,s} are spectral and conjecture that all the subsets with at least 3s/4 integers are spectral.

A graph G is H-saturated if G does not contain H as a subgraph but for any nonadjacent vertices u and v, G+uv contains H as a subgraph. The parameter sat(H,n) is the minimum number of edges in an H-saturated graph of order n. In this paper, we determine sat(H,n) for sufficiently large n when H is a union of cliques of the same order, an arbitrary union of two cliques and a generalized friendship graph.

Given integers k,s,t with [email protected][email protected]?t and k>=0, a (k,t,s)-linear forest F is a graph that is the vertex disjoint union of t paths with a total of k edges and with s of the paths being single vertices. If the number of single vertex paths is not critical, the forest F will simply be called a (k,t)-linear forest. A graph G of order n>=k+t is (k,t)-hamiltonian if for any (k,t)-linear forest F there is a hamiltonian cycle containing F. More generally, given integers m and n with [email protected][email protected]?n, a graph G of order n is (k,t,s,m)-pancyclic if for any (k,t,s)-linear forest F and for each integer r with [email protected][email protected]?n, there is a cycle of length r containing the linear forest F. Minimum degree conditions and minimum sum of degree conditions of nonadjacent vertices that imply that a graph is (k,t,s,m)-pancyclic (or just (k,t,m)-pancyclic) are proved.

A graph G is H-saturated if H is not a subgraph of G but the addition of any edge from G̅ to G results in a copy of H. The minimum size of an H-saturated graph on n vertices is denoted sat(n,H), while the maximum size is the well studied extremal number, ex(n,H). The saturation spectrum for a graph H is the set of sizes of H saturated graphs between sat(n,H) and ex(n,H). In this paper we completely determine the saturation spectrum of stars and we show the saturation spectrum of paths is continuous from sat(n, Pk) to within a constant of ex(n, Pk) when n is sufficiently large.

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 n>=3. Dirac's theorem says that if the minimum degree of G is at least 12n, then G has a hamiltonian cycle. Furthermore, Brandt et al. [J. Graph Theory 24 (1997) 165-173] proved that if n>=8, 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 12(|G|-1) 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 n>=6 and minimum degree at least 512n+2 has a 2-factor with two components.

Given positive integers k ≤ m ≤ n, a graph G of order n is (k, m)-pancyclic ordered if for any set of k vertices of G and any integer r with m ≤ r ≤ n, there is a cycle of length r encountering the k vertices in a specified order. Minimum degree conditions that imply a graph of sufficiently large order n is (k, m)-pancylic ordered are proved. Examples showing that these constraints are best possible are also provided.

Seymour conjectured for a fixed integer k ≥ 2 that if G is a graph of order n with δ ( G ) ≥ k n / ( k + 1 ) , then G contains the k th power C n k of a Hamiltonian cycle C n of G , and this minimum degree condition is sharp. Earlier the k = 2 case was conjectured by Posa. This was verified by Komlos et al. [4] . For s ≥ 3 , a graph is K 1 , s -free if it does not contain an induced subgraph isomorphic to K 1 , s . Such graphs will be referred to as generalized claw-free graphs . Minimum degree conditions that imply that a generalized claw-free graph G of sufficiently large order n contains a k th power of a Hamiltonian cycle will be proved. More specifically, it will be shown that for any ϵ > 0 and for n sufficiently large, any K 1 , s -free graph of order n with δ ( G ) ≥ ( 1 / 2 + ϵ ) n contains a C n k .

In this paper we generalize a Theorem of Jung which shows that 1-tough graphs with δ ( G ) ⩾ | V ( G ) | - 4 2 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 k cycles, for any k such that 1 ⩽ k ⩽ n - 16 4 .

Given a family of (hyper)graphs $\mathcal{F}$ a (hyper)graph $G$ is said to be $\mathcal{F}$-saturated if $G$ is $F$-free for any $F \in\mathcal{F}$ but for any edge e in the complement of $G$ the (hyper)graph $G + e$ contains some $F\in\mathcal{F}$. We survey the problem of determining the minimum size of an $\mathcal{F}$-saturated (hyper)graph and collect many open problems and conjectures.

The local independence number αi(G) of a graph G at a distance i is the maximum number of independent vertices at distance i from any vertex. We study the impact of restricting αi(G) on the (global) independence number α(G). Among others, we show that in graphs with bounded diameter, α(G) is bounded if and only if αi(G) is bounded for at least one i, 2⩽i⩽(diam(G)−1)/4.

A generalized (i,j,k)-net Ni,j,k is the graph obtained by identifying each of the vertices of a triangle with an endvertex of one of three vertex-disjoint paths of lengths i,j,k. We prove that every 2-connected claw-free N1,2,j-free graph of diameter at least max{7,2j} (j⩾2) is hamiltonian.

It is proven that if G is a 3‐connected claw‐free graph which is also H1‐free (where H1 consists of two disjoint triangles connected by an edge), then G is hamiltonian‐connected. Also, examples will be described that determine a finite family of graphs ${\cal L}$equation image such that if a 3‐connected graph being claw‐free and L‐free implies G is hamiltonian‐connected, then L $\in \cal L$equation image

Given a monotone graphical property Q, how large should d(n) be to ensure that if (Hn) is any sequence of graphs satisfying |Hn|=n and δ(Hn)⩾d(n), then almost every induced subgraph of Hn has property Q? We prove essentially best possible results for the following monotone properties: (i) k-connected for fixed k, (ii) Hamiltonian.

In this paper we characterize those forbidden triples of graphs, no one of which is a generalized claw, sufficient to imply that a 2-connected graph of sufficiently large order is hamiltonian.

For a fixed graph $H$, a graph $G$ is $H$-saturated if there is no copy of $H$ in $G$, but for any edge $e \notin G$, there is a copy of $H$ in $G + e$. The collection of $H$-saturated graphs of order $n$ is denoted by ${\bf SAT}(n,H)$, and the saturation number, ${\bf sat}(n, H),$ is the minimum number of edges in a graph in ${\bf SAT}(n,H)$. Let $T_k$ be a tree on $k$ vertices. The saturation numbers ${\bf sat}(n,T_k)$ for some families of trees will be determined precisely. Some classes of trees for which ${\bf sat}(n, T_k) < n$ will be identified, and trees $T_k$ in which graphs in ${\bf SAT}(n,T_k)$ are forests will be presented. Also, families of trees for which ${\bf sat}(n,T_k) \geq n$ will be presented. The maximum and minimum values of ${\bf sat}(n,T_k)$ for the class of all trees will be given. Some properties of ${\bf sat}(n,T_k)$ and ${\bf SAT} (n,T_k)$ for trees will be discussed.

Let N ( n , k ) be the minimum number of pairwise edge disjoint monochromatic complete graphs K k in any 2-coloring of the edges of a K n . Upper and lower bounds on N ( n , k ) will be given for k ⩾3. For k =3, exact values will be given for n ⩽11, and these will be used to give a lower bound for N ( n ,3).

For a positive integer k, a graph G is k-ordered if for every ordered set of k vertices, there is a cycle that encounters the vertices of the set in the given order. If the cycle is also a hamiltonian cycle, then G is said to be k-ordered hamiltonian. This was a concept that was introduced by Ng and Schultz. There has been a series of results involving degree conditions, generalized degree conditions, neighborhood conditions, and forbidden subgraph conditions that imply k-ordered or k-ordered hamiltonian. There have also been results dealing with the same type of conditions for bipartite graphs. Results of this nature will be surveyed.

It will be shown that if G is a graph of order n which contains a triangle, a cycle of length n or n−1 and at least cn odd cycles of different lengths for some positive constant c, then there exists some positive constant k=k(c) such that G contains at least kn 1/6 even cycles of different lengths. Other results on the number of even cycle lengths which appear in graphs with many different odd length cycles will be given.

Dirac and Ore-type degree conditions are given for a graph to contain vertex disjoint cycles each of which contains a previously specified edge. One set of conditions is given that imply vertex disjoint cycles of length at most 4, and another set of conditions are given that imply the existence of cycles that span all of the vertices of the graph (i.e. a 2-factor). The conditions are shown to be sharp and give positive answers to conjectures of Enomoto in [3] and Wang in [5].

In the study of hamiltonian graphs, many well known results use degree conditions to ensure sufficient edge density for the existence of a hamiltonian cycle. Recently it was shown that the classic degree conditions of Dirac and Ore actually imply far more than the existence of a hamiltonian cycle in a graph G, but also the existence of a 2-factor with exactly k cycles, where . In this paper we continue to study the number of cycles in 2-factors. Here we consider the well-known result of Moon and Moser which implies the existence of a hamiltonian cycle in a balanced bipartite graph of order 2n. We show that a related degree condition also implies the existence of a 2-factor with exactly k cycles in a balanced bipartite graph of order 2n with .

Let G be a graph of order n and circumference c(G). Let [email protected]? be the complement of G. We prove that max{c(G),c([email protected]?)}>[email protected][email protected]? and show sharpness of this bound.

A graph is said claw-free if it contains no induced subgraph isomorphic to K1,3. We prove that if G is a claw-free graph with minimum degree δ⩾4, then G contains a 2-factor with at most 6n/(δ+2)−1 components. Moreover, together with a theorem of Choudoum and Paulraj (J. Graph Theory 15 (1991) 259–265) and one of Anstee (J. Algorithms 6 (1985) 112–131), it is polynomial (in O(n3)) to construct such a 2-factor.

This paper determines lower bounds on the number of different cycle lengths in a graph of given minimum degree k and girth g. The most general result gives a lower bound of ckg/8.

Suppose that n ⩾ 2t + 2 (t ⩾ 17). Let G be a graph with n vertices such that its complement is connected and, for all distinct non-adjacent vertices u and v, there are at least t common neighbours. Then we prove that |E(G)|≥⌈ (2t+1)n−2t 2 -3) 2 (n≤3t−1) and |E(G)z.sfnc;≥(t+1)n−t 2 −t−3 (n≥3t). Furthermore, the results are sharp.