Page 1

Displaying 1 – 14 of 14

Showing per page

Hamilton cycles in almost distance-hereditary graphs

Bing Chen, Bo Ning (2016)

Open Mathematics

Let G be a graph on n ≥ 3 vertices. A graph G is almost distance-hereditary if each connected induced subgraph H of G has the property dH(x, y) ≤ dG(x, y) + 1 for any pair of vertices x, y ∈ V(H). Adopting the terminology introduced by Broersma et al. and Čada, a graph G is called 1-heavy if at least one of the end vertices of each induced subgraph of G isomorphic to K1,3 (a claw) has degree at least n/2, and is called claw-heavy if each claw of G has a pair of end vertices with degree sum at least...

Hamiltonian colorings of graphs with long cycles

Ladislav Nebeský (2003)

Mathematica Bohemica

By a hamiltonian coloring of a connected graph G of order n 1 we mean a mapping c of V ( G ) into the set of all positive integers such that | c ( x ) - c ( y ) | n - 1 - D G ( x , y ) (where D G ( x , y ) denotes the length of a longest x - y path in G ) for all distinct x , y G . In this paper we study hamiltonian colorings of non-hamiltonian connected graphs with long cycles, mainly of connected graphs of order n 5 with circumference n - 2 .

Hamiltonicity in multitriangular graphs

Peter J. Owens, Hansjoachim Walther (1995)

Discussiones Mathematicae Graph Theory

The family of 5-valent polyhedral graphs whose faces are all triangles or 3s-gons, s ≥ 9, is shown to contain non-hamiltonian graphs and to have a shortness exponent smaller than one.

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

Histories in path graphs

Ludovít Niepel (2007)

Discussiones Mathematicae Graph Theory

For a given graph G and a positive integer r the r-path graph, P r ( G ) , has for vertices the set of all paths of length r in G. Two vertices are adjacent when the intersection of the corresponding paths forms a path of length r-1, and their union forms either a cycle or a path of length k+1 in G. Let P r k ( G ) be the k-iteration of r-path graph operator on a connected graph G. Let H be a subgraph of P r k ( G ) . The k-history P r - k ( H ) is a subgraph of G that is induced by all edges that take part in the recursive definition of...

Homomorphism duality for rooted oriented paths

Petra Smolíková (2000)

Commentationes Mathematicae Universitatis Carolinae

Let ( H , r ) be a fixed rooted digraph. The ( H , r ) -coloring problem is the problem of deciding for which rooted digraphs ( G , s ) there is a homomorphism f : G H which maps the vertex s to the vertex r . Let ( H , r ) be a rooted oriented path. In this case we characterize the nonexistence of such a homomorphism by the existence of a rooted oriented cycle ( C , q ) , which is homomorphic to ( G , s ) but not homomorphic to ( H , r ) . Such a property of the digraph ( H , r ) is called rooted cycle duality or * -cycle duality. This extends the analogical result for...

Currently displaying 1 – 14 of 14

Page 1