From roots to paths: graphs simultaneously irregular with respect to rooted and ordinary paths

Tatiana Dovzhenok

combinatorics

From roots to paths: graphs simultaneously irregular with respect to rooted and ordinary paths

arXiv:2607.11700

summary

The paper constructs infinite families of graphs that are simultaneously irregular with respect to counting all path subgraphs and counting rooted path subgraphs for all path lengths up to a given bound, confirming a conjecture for paths.

Abstract

Let $P_{n}$ denote a path on $n$ vertices. A simple finite graph $G$ is called $P_{n}$ -irregular if any two distinct vertices of $G$ belong to a different number of subgraphs of $G$ isomorphic to $P_{n}$ . Alternatively, for a fixed vertex $r$ of $P_{n}$ (the root), $G$ is called $(P_{n})_{r}$ -irregular if any two distinct vertices of $G$ act as the root $r$ in a different number of subgraphs of $G$ isomorphic to $P_{n}$ . This paper proves that for each integer $k \geq 4$ , there exists an infinite family of graphs that are simultaneously $P_{n}$ -irregular and $(P_{n})_{r}$ -irregular for every integer $n$ satisfying $4 \leq n \leq k$ and every root $r$ of $P_{n}$ . For the path $P_{3}$ , we observe that no nontrivial $(P_{3})_{r}$ -irregular graphs exist if $r$ is the central vertex. In contrast, if $r$ is an end-vertex of $P_{3}$ , an infinite collection of graphs is constructed that are both $P_{3}$ -irregular and $(P_{3})_{r}$ -irregular. In particular, these results confirm the Strong Conjecture about $F$ -irregular graphs for the case where $F$ is a path $P_{n}$ .

29 pages, 4 figures

Topics & keywords

#graph theory #irregular graphs #path subgraphs #rooted paths #graph constructionsP_n-irregular(P_n)_r-irregularstrong conjecturesubgraph countinginfinite graph families