Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
DE
EN
Books
Journals
Events
Topic Page
Marketing
Start single access now
Access for companies
12th International Engine Congress 2025 | 25. + 26. February 2025

Meeting Place for the Powertrain and Sustainable Fuels Community

The congress will examine the future role of the internal combustion engine and its non-fossil fuels from a global perspective with leading experts. Be part of it! More information and booking options are available on our website.
EXTENDED SEARCH
Log in
Top
Published in:
Read chapter Read first chapter

2024 | OriginalPaper | Chapter

On Decompositions of the Johnson Graph

Authors : Atif Abueida, Mike Daven

Published in: Combinatorics, Graph Theory and Computing

Publisher: Springer Nature Switzerland

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Most of the results on graph decompositions involve a partition of the edges of the complete graph, complete bipartite graph, or complete multipartite graph into disjoint copies of one or more small graphs. In this chapter we find conditions for the decompositions of the Johnson graph into a variety of smaller subgraphs including cycles, path, and other common subgraphs.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Decomposing the -Fold Complete 3-Uniform Hypergraph into the Lines of the Pasch Configuration
next chapter Tiling With Three Element Sets
Literature
1.
A. Abueida and M. Daven, Multidesigns for graph-pairs on 4 and 5 vertices, Graphs & Combin., 19(4) (2003), 433–447.MathSciNetCrossRef
2.
A. Abueida and M. Daven, Multidecompositions of the complete graph, Ars Combin. 72 (2004), 17–22.MathSciNet
3.
A. Abueida and M. Daven, Decomposition of the Johnson Graphs into Graph-Pairs of Order 4, \(52^{nd}\) Southeastern International Conference on Combinatorics, Graph Theory and Computing 2021, Springer Proceedings in Mathematics and Statistics, 448 (2024), 65–71.
4.
A. Abueida and C. Lian, On the decompositions of complete graphs into cycles and stars on the same number of edges, Discuss. Math. Graph Theory, 34 (2014), 113–125.MathSciNetCrossRef
5.
P. Adams, D. Bryant, and M. Buchanan, A survey on the existence of G-designs, J. Combin. Des. 16, 373–410 (2008).MathSciNetCrossRef
6.
B. Alspach and H. Gavlas, Cycle decompositions of \(K_n\) and \(K_n-I\), J. Combin. Theory Ser. B 81 (2001), no. 1, 77–99.
7.
L.D. Andersen, Factorizations of graphs. In: C. Colbourn and J. Dinitz (eds.), The CRC Handbook of Combinatorial Designs, CRC Press, Boca Raton (1996).
8.
J. Bosák: Decomposition of graphs, Kluwer Academic Publishers, Boston (1990).
9.
M.C. Cuaresma, M. Giudici, and C.E. Praeger, Homogeneous factorisations of Johnson graphs. Des. Codes Cryptogr., 46 (2008), no. 3, 303–327.MathSciNetCrossRef
10.
A. Devillers, M. Giudici, C.H. Li, and C.E. Praeger, Primitive decompositions of Johnson graphs, J. Combin. Theory Ser. A, 115 (2008), no. 6, 925–966.MathSciNetCrossRef
11.
S. Jeevadoss and A. Muthusamy, Decomposition of complete bipartite graphs into paths and cycles, Discrete Math., 331 (2014), 98–108.MathSciNetCrossRef
12.
H.-C. Lee and Z.C. Chen, Decomposing the complete graph into Hamiltonian paths (cycles) and 3-stars. Discuss. Math. Graph Theory, 40 (2020), no. 3, 823–839.MathSciNetCrossRef
13.
C.C. Lindner and C.A. Rodger: Design theory, CRC Press, Boca Raton (1997).
14.
C.C. Lindner and C.A. Rodger, Decompositions into cycles II: cycle systems, in Contemporary design theory: a collection of surveys (edited by J. Dinitz and D. Stinson), John Wiley and Sons, New York (1992), 325–369.
15.
G. Ringel, Problem 25, in theory of graphs and its applications. In: Proceedings of the Symposium Smolenice, Prague, p. 162 (1963).
16.
M. Šajna, On decomposing \(K_n-I\) into cycles of a fixed odd length, Algebraic and topological methods in graph theory, Discrete Math. 244 (2002), no. 1–3, 435–444.
17.
G. Sethuraman and V. Murugan, Decomposition of complete graphs into arbitrary trees. Graphs Combin. 37 (2021), no. 4, 1191–1203.MathSciNetCrossRef
18.
19.
T.W. Shyu, Decompositions of complete graphs into paths and cycles, Ars Combin. 97 (2010), 257–270.MathSciNet
20.
21.
T.W. Shyu, Decompositions of complete bipartite graphs and complete graphs into paths, stars, and cycles with four edges each. Discuss. Math. Graph Theory 41 (2021), no. 2, 451–468.MathSciNetCrossRef
22.
M. Tarsi, Decomposition of a complete multigraph into simple paths: nonbalanced handcuffed designs. J. Combin. Theory Ser. A 34(1) (1983), 60–70.MathSciNetCrossRef
Metadata
Title
On Decompositions of the Johnson Graph
Authors
Atif Abueida
Mike Daven
Copyright Year
2024
Book
Combinatorics, Graph Theory and Computing

Print ISBN: 978-3-031-62165-9

Electronic ISBN: 978-3-031-62166-6

Copyright Year: 2024

DOI
https://doi.org/10.1007/978-3-031-62166-6_23

Premium Partner

    Image Credits