Orthogonal double covers of complete graphs by caterpillars of diameter 5

Research output: Contribution to journalArticlepeer-review

Abstract

An orthogonal double cover (ODC) of the complete graph K n by a graph G is a collection [InlineMediaObject not available: see fulltext.] = {G i |i = 1,2, . . . ,n} of spanning subgraphs of K n , all isomorphic to G, with the property that every edge of K n belongs to exactly two members of [InlineMediaObject not available: see fulltext.] and any two distinct members of [InlineMediaObject not available: see fulltext.] share exactly one edge. A caterpillar of diameter five is a tree arising from a path with six vertices by attaching pendant vertices to some or each of its vertices of degree two. We show that for any caterpillar of diameter five there exists an ODC of the complete graph K n .

Original languageEnglish (US)
Pages (from-to)145-163
Number of pages19
JournalGraphs and Combinatorics
Volume23
Issue number2
DOIs
StatePublished - Apr 1 2007

Keywords

  • Orthogonal double cover
  • Orthogonal labeling

Fingerprint Dive into the research topics of 'Orthogonal double covers of complete graphs by caterpillars of diameter 5'. Together they form a unique fingerprint.

Cite this