Browsing by Subject "graph labeling"

Now showing 1 - 4 of 4

Access status: Open Access ,
A note on distance labeling of graphs
(Wydawnictwa AGH, 2025) Casselgren, Carl Johan; Henricsson, Anders
We study labelings of connected graphs $G$ using labels $1,\ldots,|V(G)|$ encoding the distances between vertices in $G$. Following Lennerstad and Eriksson [Electron. J. Graph Theory Appl. 6 (2018), 152-165], we say that a graph $G$ which has a labeling $c$ satisfying that $d(u,v) \lt d(x,y) \Rightarrow c(u,v) \leq c(x,y)$, where $c(u,v) = |c(u) - c(v)|$, is a list graph. We show that these graphs are very restricted in nature and enjoy very strong structural properties. Relaxing this condition, we say that a vertex $u$ in a graph $G$ with a labeling $c$ is list-distance consistent if $d(u,v) \leq d(u,w)$ holds for all vertices $v$, $w$ satisfying that $c(u,w) = c(u,v)+1$. The maximum $k$ such that $G$ has a labeling where $k$ vertices are list-distance consistent is the list-distance consistency $\operatorname{ldc}(G)$ of $G$; if $\operatorname{ldc}(G) = |V(G)|$, then $G$ is a local list graph. We prove a structural theorem characterizing local list graphs implying that they are a quite restricted family of graphs; this answers a question of Lennerstad. Furthermore, we investigate the parameter $\operatorname{ldc}(G)$ for various classes of graphs. In particular, we prove that for all $k$, $n$ satisfying $4 \leq k \leq n$ there is a graph $G$ with $n$ vertices and $\operatorname{ldc}(G)=k$, and demonstrate that there are large classes of graphs $G$ satisfying $\operatorname{ldc}(G) = 1$. Indeed, we prove that almost every graph have this property, which implies that graphs $G$ satisfying $\operatorname{ldc}(G) \gt 1$ are in a sense quite rare (let alone local list graphs). We also suggest further variations on the topic of list graphs for future research.
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 ,
Twierdzenie Brooksa dla rozróżniającej liczby chromatycznej
(Data obrony: 2014-09-11) Wojciechowski, Marcin
Wydział Matematyki Stosowanej
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.