Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Spanning Tree Decompositions of Complete Graphs Orthogonal to Rotational 1-Factorizations

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

In Krussel et al. (ARS Comb 57:77–82, 2000), Krussel, Marshall, and Verall proved that whenever \(2n-1\) is a prime of the form \(8m+7\), there exists a spanning tree decomposition of \(K_{2n}\) orthogonal to the 1-factorization \(GK_{2n}\). In this paper, we develop a technique for constructing spanning tree decompositions that are orthogonal to rotational 1-factorizations of \(K_{2n}\). We apply our results to show that, for every \(n>2\), there exists a spanning tree decomposition orthogonal to \(GK_{2n}\). We include similar applications to other rotational families of 1-factorizations, and provide directions for further research.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Brualdi, R.A., Hollingsworth, S.: Multicolored trees in complete graphs. J. Combin. Theory Ser. B 68, 310–313 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  2. Cameron, P.J.: Parallelisms of Complete Designs. London Math. Soc., Lecture Note Series, vol. 23. Cambridge Univ. Press, Cambridge (1976)

    Book  MATH  Google Scholar 

  3. Krussel, J., Marshall, S., Verrall, H.: Spanning trees orthogonal to 1-factorizations of \({K}_{2n}\). ARS Comb. 57, 77–82 (2000)

    MathSciNet  MATH  Google Scholar 

  4. Mazzuoccolo, G., Rinaldi, G.: \(k\)-pyramidal one-factorizations. Graphs Combin. 23, 315–326 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  5. Mendelsohn, E., Rosa, A.: One-factorizations of the complete graph - a survey. J. Graph Theory 9, 43–65 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  6. Wallis, W.D.: One-Factorizations, volume 390 of Mathematics and Its Applications. Springer (1997)

  7. West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice-Hall, Upper Saddle River (2001)

    Google Scholar 

  8. Wolff, K.E.: Fast-blockplaene. Mitt. math. Sem. Giessen 102, 72–73 (1973)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Portland State University, Portland, OR, 97207, USA

    John Caughman & James Mahoney

  2. Lewis and Clark College, Portland, OR, 97219, USA

    John Krussel

Authors
  1. John Caughman
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. John Krussel
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. James Mahoney
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to John Caughman.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Caughman, J., Krussel, J. & Mahoney, J. Spanning Tree Decompositions of Complete Graphs Orthogonal to Rotational 1-Factorizations. Graphs and Combinatorics 33, 321–333 (2017). https://doi.org/10.1007/s00373-017-1766-7

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-017-1766-7

Keywords

Mathematics Subject Classification

Search

Navigation