The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “Colouring of cycles in the de Bruijn graphs”

Star-Cycle Factors of Graphs

Yoshimi Egawa, Mikio Kano, Zheng Yan (2014)

Discussiones Mathematicae Graph Theory

Similarity:

A spanning subgraph F of a graph G is called a star-cycle factor of G if each component of F is a star or cycle. Let G be a graph and f : V (G) → {1, 2, 3, . . .} be a function. Let W = {v ∈ V (G) : f(v) = 1}. Under this notation, it was proved by Berge and Las Vergnas that G has a star-cycle factor F with the property that (i) if a component D of F is a star with center v, then degF (v) ≤ f(v), and (ii) if a component D of F is a cycle, then V (D) ⊆ W if and only if iso(G − S) ≤ Σx∈S...

The cycle-complete graph Ramsey number r(C₅,K₇)

Ingo Schiermeyer (2005)

Discussiones Mathematicae Graph Theory

Similarity:

The cycle-complete graph Ramsey number r(Cₘ,Kₙ) is the smallest integer N such that every graph G of order N contains a cycle Cₘ on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erdős, Faudree, Rousseau and Schelp that r(Cₘ,Kₙ) = (m-1)(n-1)+1 for all m ≥ n ≥ 3 (except r(C₃,K₃) = 6). This conjecture holds for 3 ≤ n ≤ 6. In this paper we will present a proof for r(C₅,K₇) = 25.

The list linear arboricity of planar graphs

Xinhui An, Baoyindureng Wu (2009)

Discussiones Mathematicae Graph Theory

Similarity:

The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. An and Wu introduce the notion of list linear arboricity lla(G) of a graph G and conjecture that lla(G) = la(G) for any graph G. We confirm that this conjecture is true for any planar graph having Δ ≥ 13, or for any planar graph with Δ ≥ 7 and without i-cycles for some i ∈ {3,4,5}. We also prove that ⌈½Δ(G)⌉ ≤ lla(G) ≤ ⌈½(Δ(G)+1)⌉ for any planar graph having Δ ≥ 9. ...

Supermagic Graphs Having a Saturated Vertex

Jaroslav Ivančo, Tatiana Polláková (2014)

Discussiones Mathematicae Graph Theory

Similarity:

A graph is called supermagic if it admits a labeling of the edges by pairwise different consecutive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In this paper we establish some conditions for graphs with a saturated vertex to be supermagic. Inter alia we show that complete multipartite graphs K1,n,n and K1,2,...,2 are supermagic.

The i-chords of cycles and paths

Terry A. McKee (2012)

Discussiones Mathematicae Graph Theory

Similarity:

An i-chord of a cycle or path is an edge whose endpoints are a distance i ≥ 2 apart along the cycle or path. Motivated by many standard graph classes being describable by the existence of chords, we investigate what happens when i-chords are required for specific values of i. Results include the following: A graph is strongly chordal if and only if, for i ∈ {4,6}, every cycle C with |V(C)| ≥ i has an (i/2)-chord. A graph is a threshold graph if and only if, for i ∈ {4,5}, every path...