Decomposition of complete graphs into small graphs | Zendy

Dalibor Fronček | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Decomposition of complete graphs into small graphs

Author(s) -

Dalibor Fronček

Publication year - 2010

Publication title -

opuscula mathematica

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.481

H-Index - 16

eISSN - 2300-6919

pISSN - 1232-9274

DOI - 10.7494/opmath.2010.30.3.277

Subject(s) - mathematics , combinatorics , decomposition , indifference graph , chordal graph , modular decomposition , pathwidth , discrete mathematics , graph , line graph , chemistry , organic chemistry

In 1967, A. Rosa proved that if a bipartite graph \(G\) with \(n\) edges has an \(\alpha\)-labeling, then for any positive integer \(p\) the complete graph \(K_{2np+1}\) can be cyclically decomposed into copies of \(G\). This has become a part of graph theory folklore since then. In this note we prove a generalization of this result. We show that every bipartite graph \(H\) which decomposes \(K_k\) and \(K_m\) also decomposes \(K_{km}\)

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research