Search

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 .

This article examines the recent emergence of online debates about Day of the Dead music, one of countless sites worldwide where conversations about diversity take place in the shadow of state policies. There, people engage diversity not through the state-centric “managerial discourse” of “diversity talk” but through localized interpretations of sameness and difference. I discuss the social effects of semiotic processes through which people consider sameness and difference: the emergence of a regional venue for debating contentious issues and the consolidation of an implicit consensus of linguistic practice. Attending to local understandings of difference can reduce the risk of taking state-sponsored views of (linguistic) diversity as natural kinds while recovering diversity and surrounding ideologies as ethnographic objects.

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 .

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.

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.

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.

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.

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 .

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.

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.

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.

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.

In this paper we characterize those pairs of forbidden subgraphs sufficient to imply various hamiltonian type properties in graphs. In particular, we find all forbidden pairs sufficient, along with a minor connectivity condition, to imply a graph is traceable, hamiltonian, pancyclic, panconnected or cycle extendable. We also consider the case of hamiltonian-connected graphs and present a result concerning the pairs for such graphs.

In this paper we summarize known results on claw-free graphs. The paper is subdivided into the following chapters and sections: 1. 1. Introduction 2. 2. Paths, cycles, hamiltonicity 2.1. (a) Preliminaries 2.2. (b) Degree and neighborhood conditions 2.3. (c) Local connectivity conditions 2.4. (d) Further forbidden subgraphs 2.5. (e) Invariants 2.6. (f) Squares 2.7. (g) Regular graphs 2.8. (h) Other hamiltonicity related results and generalizations 2.9. 3. Matchings and factors 2.10. 4. Independence, domination, other invariants and extremal problems 2.11. 5. Algorithmic aspects 2.12. 6. Miscellaneous 2.13. 7. Appendix — List of all 2-connected nonhamiltonian claw-free graphs on n ⩽ 12 vertices.

The k-spectrum sk(G) of a graph G is the set of all positive integers that occur as the size of an induced k-vertex subgraph of G. In this paper we determine the minimum order and size of a graph G with sk (G) = {0, 1, …,(2k)} and consider the more general question of describing those sets S ⊆ {0,1, … ,(2k)} such that S = sk(G) for some graph G.

We investigate whether K r -free graphs with few repetitions in the degree sequence may have independence number o( n ). We settle the cases r = 3 and r ⩾ 5, and give partial results for the very interesting case r = 4.

A non-Hamiltonian cycle C in a graph G is extendable if there is a cycle C ′ in G with V ( C ′) ⊃ V ( C ) with one more vertex than C . For any integer k ⩾ 0, a cycle C is k -chord extendable if it is extendable to the cycle C ′ using at most k of the chords of the cycle C . It will be shown that if G is a graph of order n , then δ ( G ) > 3 n /4 − 1 implies that any proper cycle is 0-chord extendable, δ ( G ) > 5 n /9 implies that any proper cycle is 1-chord extendable, and δ ( G ) > [ n /2] implies that any proper cycle is 2-chord extendable. Also, each of these results is sharp in the sense that the minimum degree condition cannot, in general, be lowered.

Let ( x , y ) be an edge of a graph G . Then the rotation of ( x , y ) about x is the operation of removing ( x , y ) from G and inserting ( x , y ′) as an edge, where y ′ is a vertex of G . The rotation distance between graphs G and H is the minimum number of rotations necessary to transform G into H . Lower and upper bounds are given on the rotation distance of two graphs in terms of their greatest common subgraphs and their partial rotation link of largest cardinality. We also propose some extermal problems for the rotation distance of trees.

For a positive integer n and a graphical property P, extn(P) will denote the minimal number of edges in a graph G of order n that satisfies property P, and Ext>n(P) will denote the class of graphs with n vertices and extn(P) edges that have property P. The extremal numbers extn(P) for properties P that have been commonly used as sufficient conditions for Hamiltonian paths and cycles in graphs will be investigated. In particular, results on the extremal numbers for the generalized degree and generalized independent degree properties will be given, where for a fixed positive integer t, the generalized degree δt(G) (generalized independent degree δit(G)) is the minimum number of vertices in the union of the neighborhoods of a set of t (independent) vertices of the graph G.

Dirac proved that if each vertex of a graph G of order n ⩾3 has degree at least n /2, then the graph is Hamiltonian. This result will be generalized by showing that if the union of the neighborhoods of each pair of vertices of a 2-connected graph G of sufficiently large order n has at least n /2 vertices, then G is Hamiltonian. Other results that are based on neighborhood unions of pairs of vertices will be proved that give the existence of cycles, paths and matchings. Also, Hamiltonian results will be considered that use the union of neighborhoods of more than 2 vertices.

We investigate the minimum, taken over all graphs G with n vertices and at least ⌊ n 2 /4⌋ + 1 edges, of the number of vertices and edges of G which are on cycles of length 2 k + 1.

RecentlywedeterminedtheRamseyNumber r ( C 7 ,C 7 ,C 7 )=25 . Let G =( V ( G ) ,E ( G )) be an undirected finite graph without any loops ormultipleedges,where V ( G )denotesitsvertexsetand E ( G )itsedgeset.Inthefollowingwewilloftenconsiderthecompletegraph K p on p verticesandthecycle C p on p vertices.A k− coloring( F 1 ,F 2 ,...,F k )ofagraph G isacoloringoftheedgesof G withatmost k differentcolors F 1 ,...,F k . Thegraph =( V ( G ) ,E ( F i ))denotesthesubgraphof G whichconsistsofallverticesof G andalledgeswhicharecoloredwithcolor F i . Wesaythat K p −→ ( G 1 ,G 2 ,...,G k ) , if ineach k− coloring of K p thesubgraph contains a graph isomorphic to G i for at least one i with 1 ≤ i ≤ k. Nowthe Ramsey Number of k graphs G 1 ,G 2 ,...,G k is defined as the minimalinteger p such that K p −→ ( G 1 ,...,G k )( r ( G 1 ,...,G k ):= min{p|K p −→ ( G 1 ,...,G k ) } ).A goodand detailed overview about known estimations and exact values isgiveninRadziszowski’ssurvey’SmallRamseyNumbers’,[8].We have a general lower bound only in the case

For k ⩾ 2, any graph G with n vertices and (k−1)(n−k+2)+(2k−2) edges has a subrgraph of minimum degree at least k; however, this subgraph need not be proper. It is shown that if G has at least (k−1)(n−k+2)+(2k−2)+1 edges, then there is a subgraph H of minimal degree k that has at most n − √n;√6k3vertices. Also, conditions that insure the existense of smaller subgraphs of minimum degree k are given.