All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 6 Next

Displaying 101 – 120 of 238

Showing per page

Hamiltonicity of cubic Cayley graphs

Henry Glover, Dragan Marušič (2007)

Journal of the European Mathematical Society

Following a problem posed by Lovász in 1969, it is believed that every finite connected vertex-transitive graph has a Hamilton path. This is shown here to be true for cubic Cayley graphs arising from finite groups having a ( 2 , s , 3 ) -presentation, that is, for groups G = 〈 a , b ∣ a 2 = 1 , b s = 1 , ( a b ) 3 = 1 , ⋯ 〉 generated by an involution a and an element b of order s ≥ 3 such that their product a b has order 3 . More precisely, it is shown that the Cayley graph X = Cay ( G , { a , b , b - 1 } ) has a Hamilton cycle when | G | (and thus s ) is congruent to 2 modulo 4, and has a long cycle missing...

Hamiltonicity of k -traceable graphs.

Bullock, Frank, Dankelmann, Peter, Frick, Marietjie, Henning, Michael A., Oellermann, Ortrud R., van Aardt, Susan (2011)

The Electronic Journal of Combinatorics [electronic only]

Heavy Subgraph Conditions for Longest Cycles to Be Heavy in Graphs

Binlong Lia, Shenggui Zhang (2016)

Discussiones Mathematicae Graph Theory

Let G be a graph on n vertices. A vertex of G with degree at least n/2 is called a heavy vertex, and a cycle of G which contains all the heavy vertices of G is called a heavy cycle. In this note, we characterize graphs which contain no heavy cycles. For a given graph H, we say that G is H-heavy if every induced subgraph of G isomorphic to H contains two nonadjacent vertices with degree sum at least n. We find all the connected graphs S such that a 2-connected graph G being S-heavy implies any longest...

Heavy subgraph pairs for traceability of block-chains

Binlong Li, Hajo Broersma, Shenggui Zhang (2014)

Discussiones Mathematicae Graph Theory

A graph is called traceable if it contains a Hamilton path, i.e., a path containing all its vertices. Let G be a graph on n vertices. We say that an induced subgraph of G is o−1-heavy if it contains two nonadjacent vertices which satisfy an Ore-type degree condition for traceability, i.e., with degree sum at least n−1 in G. A block-chain is a graph whose block graph is a path, i.e., it is either a P1, P2, or a 2-connected graph, or a graph with at least one cut vertex and exactly two end-blocks....

Improved Sufficient Conditions for Hamiltonian Properties

Jens-P. Bode, Anika Fricke, Arnfried Kemnitz (2015)

Discussiones Mathematicae Graph Theory

In 1980 Bondy [2] proved that a (k+s)-connected graph of order n ≥ 3 is traceable (s = −1) or Hamiltonian (s = 0) or Hamiltonian-connected (s = 1) if the degree sum of every set of k+1 pairwise nonadjacent vertices is at least ((k+1)(n+s−1)+1)/2. It is shown in [1] that one can allow exceptional (k+ 1)-sets violating this condition and still implying the considered Hamiltonian property. In this note we generalize this result for s = −1 and s = 0 and graphs that fulfill a certain connectivity condition....

Intersection graph of gamma sets in the total graph

T. Tamizh Chelvam, T. Asir (2012)

Discussiones Mathematicae Graph Theory

In this paper, we consider the intersection graph I Γ ( ℤ ₙ ) of gamma sets in the total graph on ℤₙ. We characterize the values of n for which I Γ ( ℤ ₙ ) is complete, bipartite, cycle, chordal and planar. Further, we prove that I Γ ( ℤ ₙ ) is an Eulerian, Hamiltonian and as well as a pancyclic graph. Also we obtain the value of the independent number, the clique number, the chromatic number, the connectivity and some domination parameters of I Γ ( ℤ ₙ ) .

Isomorphisms and traversability of directed path graphs

Hajo Broersma, Xueliang Li (2002)

Discussiones Mathematicae Graph Theory

The concept of a line digraph is generalized to that of a directed path graph. The directed path graph Pₖ(D) of a digraph D is obtained by representing the directed paths on k vertices of D by vertices. Two vertices are joined by an arc whenever the corresponding directed paths in D form a directed path on k+1 vertices or form a directed cycle on k vertices in D. In this introductory paper several properties of P₃(D) are studied, in particular with respect to isomorphism and traversability. In our...

Linear forests and ordered cycles

Guantao Chen, Ralph J. Faudree, Ronald J. Gould, Michael S. Jacobson, Linda Lesniak, Florian Pfender (2004)

Discussiones Mathematicae Graph Theory

A collection L = P ¹ ∪ P ² ∪ . . . ∪ P t (1 ≤ t ≤ k) of t disjoint paths, s of them being singletons with |V(L)| = k is called a (k,t,s)-linear forest. A graph G is (k,t,s)-ordered if for every (k,t,s)-linear forest L in G there exists a cycle C in G that contains the paths of L in the designated order as subpaths. If the cycle is also a hamiltonian cycle, then G is said to be (k,t,s)-ordered hamiltonian. We give sharp sum of degree conditions for nonadjacent vertices that imply a graph is (k,t,s)-ordered hamiltonian.

Currently displaying 101 – 120 of 238