Orthogonal double covers of complete graphs by lobsters of diameter 5

Research output: Contribution to journalArticlepeer-review

Abstract

An orthogonal double cover (ODC) of the complete graph Kn by a graph G is a collection G = {Gi i = 1, 2,..., n} of spanning subgraphs of Kn, all isomorphic to G, with the property that every edge of Kn belongs to exactly two members of G and any two distinct members of G share exactly one edge. A lobster of diameter five is a tree arising from a double star by attaching any number of pendant vertices to each of its vertices of degree one. We show that for any double star R(p, q) there exists an ODC of Kn by all lobsters of diameter five (with finitely many possible exceptions) arising from R(p, q).

Original languageEnglish (US)
Pages (from-to)129-134
Number of pages6
JournalJournal of Combinatorial Mathematics and Combinatorial Computing
Volume66
StatePublished - Aug 2008

Keywords

  • Orthogonal double cover
  • Orthogonal labeling

Fingerprint

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

Cite this