𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Decompositions of regular graphs into Knc ∨ 2K2

✍ Scribed by R. Balakrishnan; R. Sampathkumar

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
437 KB
Volume
156
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The join K~ V2K2 is the graph obtained by taking a copy ofK, ~ and two disjoint copies of K2, disjoint from K c, and joining every vertex of K, c to every vertex of 2K2. In this paper we show that for each positive integer n, the graph K, ~ V 2/(2 admits a p-valuation and has gracefulness 4n + 3. Further, for any finite set So of positive integers and n ~>2Max{x E So} + 1, a new graph valuation, p(n;So), is introduced. Finally, some open problems are proposed.

📜 SIMILAR VOLUMES

Decompositions of complete graphs into r
Decompositions of complete graphs into regular bichromatic factors
✍ Anton Kotzig 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 517 KB

The proof of the following theorem is given: A complete graph with n vertkes can he decomposed into r regular bichromatic factors if and only if n is even and greater thl;iirl 4 and there exists $1 natural number k with the properties that k < r anu. ak-l < n 5 Zk.

Decompositions of complete graphs into r
Decompositions of complete graphs into regular bichromatic factors
✍ Anton Kotzig 📂 Article 📅 1972 🏛 Elsevier Science 🌐 English ⚖ 425 KB

Abstxact. The purpose of this paper is to find iI nccessar) and sufficient condition fltr the euis-trn~~ of ;L decoillposi!ion of a ~omplcte graph with given number of vc;tices into regular bichro-ma% ticfor ;uld v.1 artswcr thy' question what is the possible number of factors in such a de-c~?rnp~~i

P4-decompositions of regular graphs
P4-decompositions of regular graphs
✍ Heinrich, Katherine; Liu, Jiping; Yu, Minli 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB 👁 1 views

In this article, we show that every simple r-regular graph G admits a balanced P 4 -decomposition if r ≡ 0(mod 3) and G has no cut-edge when r is odd. We also show that a connected 4-regular graph G admits a P 4 -decomposition if and only if |E(G)| ≡ 0(mod 3) by characterizing graphs of maximum degr

Decompositions of regular bipartite grap
Decompositions of regular bipartite graphs
✍ Michael S. Jacobson; Miroslaw Truszczyński; Zsolt Tuza 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 692 KB

In this paper we discuss isomorphic decompositions of regular bipartite graphs into trees and forests. We prove that: (1) there is a wide class of r-regular bipartite graphs that are decomposable into any tree of size r, (2) every r-regular bipartite graph decomposes into any double star of size r,

Regular path decompositions of odd regul
Regular path decompositions of odd regular graphs
✍ Odile Favaron; François Genest; Mekkia Kouider 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 197 KB

## Abstract Kotzig asked in 1979 what are necessary and sufficient conditions for a __d__‐regular simple graph to admit a decomposition into paths of length __d__ for odd __d__>3. For cubic graphs, the existence of a 1‐factor is both necessary and sufficient. Even more, each 1‐factor is extendable