Decompositions of complete graphs into isomorphic bipartite subgraphs
Let \(f\) be a 1-1 mapping of \(V(G)\) into the set \(S= \{0,1,\dots,| E(G)|\}\). Then \(f\) is called a \(\beta\)-valuation of \(G\) if the induced function \(\overline f: E(G)\to S\) given by \(\overline f(uv)= | f(u)- f(v)|\), for all \(uv\in E(G)\), is 1-1. A \(\beta\)-valuation \(f\) is called \(\alpha\)-valuation of \(G\) if there exists a nonnegative number \(\lambda\) such that for every \(uv\in E(G)\) with \(f(u)< f(v)\) we have \(f(u)< \lambda< f(v)\). Let \(Q_ n(G)= G\times K_ 2\times\cdots\times K_ 2= G\times (K_ 2)^{n-1}\) denote the graph of the \(n\)-dimensional \(G\)-cube. The authors prove that for any positive integer \(n\) and \(G= K_{3,3}\), \(K_{4,4}\) and \(P_ k\) the graph \(Q_ n(G)\) has an \(\alpha\)-valuation. This result together with Rosa's theorem guarantees the decomposition of some complete graphs into certain bipartite graphs.
- The energy of a graph
- Decompositions of complete graphs and complete bipartite graphs into isomorphic supersubdivision graphs
- Decomposition of a Complete Multi-Partite Graph into Isomorphic Claws
- scientific article; zbMATH DE number 1792634 (Why is no real title available?)
- scientific article; zbMATH DE number 1409220 (Why is no real title available?)
- Decomposition of Certain Complete Graphs and Complete Multipartite Graphs into Almost-bipartite Graphs and Bipartite Graphs
- scientific article; zbMATH DE number 2188359 (Why is no real title available?)
- A note on the decomposition of graphs into isomorphic matchings
This page was built for publication: Decompositions of complete graphs into isomorphic bipartite subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1323486)
