Line‐graphical degree sequences

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

A degree sequence π = (d1, d2,…,dp), with d1 ≥ d2 ≥…≥ dp, 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 d1 = p ‐ 1, d1 = p ‐ 2, d1 ≤ 3, and d1 = dp. It is also shown that if a degree sequence with d1 = 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 C5, 2K1, + K2, K1 + 2K2, or 3K1, as an induced subgraph.

Original languageEnglish (US)
Pages (from-to)219-232
Number of pages14
JournalJournal of Graph Theory
Volume4
Issue number2
DOIs
StatePublished - Jan 1 1980

Fingerprint

Degree Sequence
Line
Line Graph
Induced Subgraph
Exception
Arbitrary
Graph in graph theory
Graphics

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Cite this

@article{735c2c612dec4953b5ca84d82bb4d2fb,
title = "Line‐graphical degree sequences",
abstract = "A degree sequence π = (d1, d2,…,dp), with d1 ≥ d2 ≥…≥ dp, 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 d1 = p ‐ 1, d1 = p ‐ 2, d1 ≤ 3, and d1 = dp. It is also shown that if a degree sequence with d1 = 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 C5, 2K1, + K2, K1 + 2K2, or 3K1, as an induced subgraph.",
author = "Douglas Bauer",
year = "1980",
month = "1",
day = "1",
doi = "https://doi.org/10.1002/jgt.3190040210",
language = "English (US)",
volume = "4",
pages = "219--232",
journal = "Journal of Graph Theory",
issn = "0364-9024",
publisher = "Wiley-Liss Inc.",
number = "2",

}

Line‐graphical degree sequences. / Bauer, Douglas.

In: Journal of Graph Theory, Vol. 4, No. 2, 01.01.1980, p. 219-232.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Line‐graphical degree sequences

AU - Bauer, Douglas

PY - 1980/1/1

Y1 - 1980/1/1

N2 - A degree sequence π = (d1, d2,…,dp), with d1 ≥ d2 ≥…≥ dp, 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 d1 = p ‐ 1, d1 = p ‐ 2, d1 ≤ 3, and d1 = dp. It is also shown that if a degree sequence with d1 = 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 C5, 2K1, + K2, K1 + 2K2, or 3K1, as an induced subgraph.

AB - A degree sequence π = (d1, d2,…,dp), with d1 ≥ d2 ≥…≥ dp, 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 d1 = p ‐ 1, d1 = p ‐ 2, d1 ≤ 3, and d1 = dp. It is also shown that if a degree sequence with d1 = 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 C5, 2K1, + K2, K1 + 2K2, or 3K1, as an induced subgraph.

UR - http://www.scopus.com/inward/record.url?scp=84936239774&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84936239774&partnerID=8YFLogxK

U2 - https://doi.org/10.1002/jgt.3190040210

DO - https://doi.org/10.1002/jgt.3190040210

M3 - Article

VL - 4

SP - 219

EP - 232

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 2

ER -