✦ LIBER ✦

Packing two copies of a sparse graph into a graph with restrained maximum degree

✍ Scribed by Hong Wang

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 132 KB
Volume: 62
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20384

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We show that if a tree T is not a star, then there is an embedding σ of T in the complement of T such that the maximum degree of T∪σ(T) is at most Δ(T)+2. We also show that if G is a graph of order n with n−1 edges, then with several exceptions, there exists an embedding σ of G in the complement of G such that the maximum degree of G∪σ(G) is at most Δ(G)+3. Both results are sharp in the sense that neither of Δ(T)+2 and Δ(G)+3 can be reduced. From these two results, we deduce two corollaries on packings of three graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 178–187, 2009

📜 SIMILAR VOLUMES

Packing Three Copies of a Tree into a Co

Packing Three Copies of a Tree into a Complete Graph

✍ Hong Wang; Norbert Sauer 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 161 KB

A covering construction for packing disj

A covering construction for packing disjoint copies of the Hoffman-Singleton graph into K50

✍ Jana Ŝiagiová; Mariusz Meszka 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB

## Abstract In this note we show how coverings induced by voltage assignments can be used to produce packings of disjoint copies of the Hoffman‐Singleton graph into __K__~50~. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 408–412, 2003; Published online in Wiley InterScience (www.interscience

Vertex decompositions of sparse graphs i

Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k

✍ O. V. Borodin; A. O. Ivanova; M. Montassier; P. Ochem; A. Raspaud 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract A graph __G__ is (__k__,0)‐colorable if its vertices can be partitioned into subsets __V__~1~ and __V__~2~ such that in __G__[__V__~1~] every vertex has degree at most __k__, while __G__[__V__~2~] is edgeless. For every integer __k__⩾0, we prove that every graph with the maximum average

Constructing a bipartite graph of maximu

Constructing a bipartite graph of maximum connectivity with prescribed degrees

✍ Asano, Takao 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 328 KB 👁 3 views

d 2,n 2 ) is a bipartite graphical sequence, if there is a bipartite graph G with degrees {D 1 , D 2 } (i.e., G has two independent vertex sets In other words, {D 1 , D 2 } is a bipartite graphical sequence if and only if there is an n 1 1 n 2 matrix of 0's and 1's having d 1j 1 1's in row j 1 and

A Note on Large Graphs of Diameter Two a

A Note on Large Graphs of Diameter Two and Given Maximum Degree

✍ Brendan D McKay; Mirka Miller; Jozef Širáň 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 242 KB

Let vt(d, 2) be the largest order of a vertex-transitive graph of degree d and diameter 2. It is known that vt(d, 2)=d 2 +1 for d=1, 2, 3, and 7; for the remaining values of d we have vt(d, 2) d 2 &1. The only known general lower bound on vt(d, 2), valid for all d, seems to be vt(d, 2) w(d+2)Â2x W(d

(d,1)-total labeling of graphs with a gi

(d,1)-total labeling of graphs with a given maximum average degree

✍ Mickaël Montassier; André Raspaud 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 166 KB 👁 1 views

## Abstract The (__d__,1)‐total number $\lambda \_{d}^{T}(G)$ of a graph __G__ is the width of the smallest range of integers that suffices to label the vertices and the edges of __G__ so that no two adjacent vertices have the same color, no two incident edges have the same color, and the distance