Wyniki wyszukiwania

1

Symmetric Hamilton Cycle Decompositions of Complete Multigraphs

100%

Chitra V., Muthusamy A.

Discussiones Mathematicae Graph Theory

|

2013

|

tom 33

|

nr 4

695-707

EN

Let n ≥ 3 and ⋋ ≥ 1 be integers. Let ⋋Kn denote the complete multigraph with edge-multiplicity ⋋. In this paper, we show that there exists a symmetric Hamilton cycle decomposition of ⋋K2m for all even ⋋ ≥ 2 and m ≥ 2. Also we show that there exists a symmetric Hamilton cycle decomposition of ⋋K2m − F for all odd ⋋ ≥ 3 and m ≥ 2. In fact, our results together with the earlier results (by Walecki and Brualdi and Schroeder) completely settle the existence of symmetric Hamilton cycle decomposition of ⋋Kn (respectively, ⋋Kn − F, where F is a 1-factor of ⋋Kn) which exist if and only if ⋋(n − 1) is even (respectively, ⋋(n − 1) is odd), except the non-existence cases n ≡ 0 or 6 (mod 8) when ⋋ = 1

2

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Decompositions of multigraphs into parts with two edges

100%

Ivančo J., Meszka M., Skupień Z.

Discussiones Mathematicae Graph Theory

|

2002

|

tom 22

|

nr 1

113-121

EN

Given a family 𝓕 of multigraphs without isolated vertices, a multigraph M is called 𝓕-decomposable if M is an edge disjoint union of multigraphs each of which is isomorphic to a member of 𝓕. We present necessary and sufficient conditions for the existence of such decompositions if 𝓕 comprises two multigraphs from the set consisting of a 2-cycle, a 2-matching and a path with two edges.

3

On Ramsey $(K_{1,2}, Kₙ)$-minimal graphs

100%

Hałuszczak M.

Discussiones Mathematicae Graph Theory

|

2012

|

tom 32

|

nr 2

331-339

EN

Let F be a graph and let 𝓖,𝓗 denote nonempty families of graphs. We write F → (𝓖,𝓗) if in any 2-coloring of edges of F with red and blue, there is a red subgraph isomorphic to some graph from G or a blue subgraph isomorphic to some graph from H. The graph F without isolated vertices is said to be a (𝓖,𝓗)-minimal graph if F → (𝓖,𝓗) and F - e not → (𝓖,𝓗) for every e ∈ E(F). We present a technique which allows to generate infinite family of (𝓖,𝓗)-minimal graphs if we know some special graphs. In particular, we show how to receive infinite family of $(K_{1,2}, Kₙ)$-minimal graphs, for every n ≥ 3.

4

1-factors and characterization of reducible faces of plane elementary bipartite graphs

88%

Taranenko A., Vesel A.

Discussiones Mathematicae Graph Theory

|

2012

|

tom 32

|

nr 2

289-297

EN

As a general case of molecular graphs of benzenoid hydrocarbons, we study plane bipartite graphs with Kekulé structures (1-factors). A bipartite graph G is called elementary if G is connected and every edge belongs to a 1-factor of G. Some properties of the minimal and the maximal 1-factor of a plane elementary graph are given. A peripheral face f of a plane elementary graph is reducible, if the removal of the internal vertices and edges of the path that is the intersection of f and the outer cycle of G results in an elementary graph. We characterize the reducible faces of a plane elementary bipartite graph. This result generalizes the characterization of reducible faces of an elementary benzenoid graph.

Ograniczanie wyników

4 Discussiones Mathematicae Graph Theory

1 Chitra V.

1 Hałuszczak M.

1 Ivančo J.

1 Meszka M.

1 Muthusamy A.

1 Skupień Z.

1 Taranenko A.

1 Vesel A.

1 2013

2 2012

1 2002

Symmetric Hamilton Cycle Decompositions of Complete Multigraphs

Decompositions of multigraphs into parts with two edges

On Ramsey $(K_{1,2}, Kₙ)$-minimal graphs

1-factors and characterization of reducible faces of plane elementary bipartite graphs