✦ LIBER ✦

Line-graphical degree sequences

✍ Scribed by Douglas Bauer

Publisher: John Wiley and Sons
Year: 1980
Tongue: English
Weight: 560 KB
Volume: 4
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190040210

No coin nor oath required. For personal study only.

✦ Synopsis

A degree sequence rr = (d,, d2, . . . , d,), with d, r d 2 r -* * 2 d,, is line graphical if it is realized by the line graph of some graph. Degree sequences with line-graphical realizations are characterized for the cases d, = p -I , d, = p -2, d, 5 3 , and d, = d,. It is also shown that if a degree sequence with d, = p -1 is line graphical, it is uniquely line graphical. It follows that with possibly one exception each line-graphical realization of an arbitrary degree sequence must have either C, , 2K, + K2, K, +2K2, or 3K, as an induced subgraph.

📜 SIMILAR VOLUMES

The smallest degree sum that yields pote

The smallest degree sum that yields potentiallyPk-graphical sequences

✍ Jiong-Sheng, Li; Zi-Xia, Song 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 354 KB 👁 2 views

A simple graph G is said to have property P k if it contains a complete subgraph of order k + 1, and a sequence π is potentially P k -graphical if it has a realization having property P k . Let σ(k, n) denote the smallest degree sum such that every n-term graphical sequence π without zero terms and

Graphic sequences have realizations cont

Graphic sequences have realizations containing bisections of large degree

✍ Stephen G. Hartke; Tyler Seacrest 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 233 KB

A __bisection__ of a graph is a balanced bipartite spanning sub‐graph. Bollobás and Scott conjectured that every graph __G__ has a bisection __H__ such that deg~__H__~(__v__) ≥ ⌊deg~__G__~(__v__)/2⌋ for all vertices __v__. We prove a degree sequence version of this conjecture: given a graphic sequen

Convexity of degree sequences

✍ Anstee, R. P.; Nam, Yunsun 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 2 views

We explore the convexity of the set of vectors consisting of degree sequences of subgraphs of a given graph. Results of Katerinis and Fraisse, Hell and Kirkpatrick concerning vertex deleted f -factors are generalized.

Sequences of graphical invariants

✍ Jerzy Topp 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 466 KB

For a given graphical invariant K, a sequence (a, , , a,, . . . , a, ) of positive integers is said to be r-feasible if there exists a graph G with distinguished vertices ul, u2, . . . , v, such that T( G) = a. and T( G -u1 -v2 ---v i ) = ai for i = 1, 2, . . . , n . In this paper, we investigate r-

Signed degree sequences and multigraphs

✍ T. S. Michael 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 59 KB

## Abstract We give necessary and sufficient conditions for the existence of a signed r‐multigraph with a prescribed signed degree sequence. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 101–105, 2002

An inequality for degree sequences

✍ L.A. Székely; L.H. Clark; R.C. Entringer 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 420 KB