Displaying similar documents to “ k -cycle free one-factorizations of complete graphs.”

The structure of digraphs associated with the congruence x k ≡ y ( mod n )

Lawrence Somer, Michal Křížek (2011)

Czechoslovak Mathematical Journal

Similarity:

We assign to each pair of positive integers n and k ≥ 2 a digraph G ( n , k ) whose set of vertices is H = { 0 , 1 , ⋯ , n - 1 } and for which there is a directed edge from a ∈ H to b ∈ H if a k ≡ b ( mod n ) . We investigate the structure of G ( n , k ) . In particular, upper bounds are given for the longest cycle in G ( n , k ) . We find subdigraphs of G ( n , k ) , called fundamental constituents of G ( n , k ) , for which all trees attached to cycle vertices are isomorphic.

On the Decompositions of Complete Graphs into Cycles and Stars on the Same Number of Edges

Atif A. Abueida, Chester Lian (2014)

Discussiones Mathematicae Graph Theory

Similarity:

Let Cm and Sm denote a cycle and a star on m edges, respectively. We investigate the decomposition of the complete graphs, Kn, into cycles and stars on the same number of edges. We give an algorithm that determines values of n, for a given value of m, where Kn is {Cm, Sm}-decomposable. We show that the obvious necessary condition is sufficient for such decompositions to exist for different values of m.