Browsing by Subject "graph decomposition"

Now showing 1 - 5 of 5

Access status: Open Access ,
Decomposition of complete graphs into small graphs
(2010) Froncek, Dalibor
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}$.
Access status: Restricted ,
Dekompozycje i pakowania grafów na podgrafy rozmiaru 3
(Data obrony: 2020-07-15) Górka, Izabela
Wydział Matematyki Stosowanej
Access status: Open Access ,
On 1-rotational decompositions of complete graphs into tripartite graphs
(Wydawnictwa AGH, 2019) Bunge, Ryan C.
Consider a tripartite graph to be any simple graph that admits a proper vertex coloring in at most 3 colors. Let $G$ be a tripartite graph with $n$ edges, one of which is a pendent edge. This paper introduces a labeling on such a graph $G$ used to achieve 1-rotational $G$-decompositions of $K_{2nt}$ for any positive integer $t$. It is also shown that if $G$ with a pendent edge is the result of adding an edge to a path on $n$ vertices, then $G$ admits such a labeling.
Access status: Open Access ,
Open trails in digraphs
(2011) Cichacz-Przeniosło, Sylwia; Görlich, Agnieszka
It has been shown in [S. Cichacz, A. Görlich, Decomposition of complete bipartite graphs into open trails, Preprint MD 022, (2006)] that any bipartite graph $K_{a,b}$, is decomposable into open trails of prescribed even lengths. In this article we consider the corresponding question for directed graphs. We show that the complete directed graphs $\overleftrightarrow{K}_n$ and $\overleftrightarrow{K}_{a,b}$ are arbitrarily decomposable into directed open trails.
Access status: Open Access ,
α2-labeling of graphs
(2009) Fronček, Dalibor
We show that if a graph $G$ on n edges allows certain special type of rosy labeling (a.k.a. $\rho$-labeling), called $\alpha_2$-labeling, then for any positive integer $k$ the complete graph $K_{2nk+1}$ can be decomposed into copies of $G$. This notion generalizes the $\alpha$-labeling introduced in 1967 by A. Rosa.