On infinite families of [Pn]-irregular graphs

Tatiana Dovzhenok; Ilya Lukashenko; Andrei Mikhalev; and Yahor Filiuta

Math & statisticsCombinatorics & discrete math

On infinite families of $[P_{n}]$ -irregular graphs

Tatiana Dovzhenok, Ilya Lukashenko, Andrei Mikhalev, and Yahor Filiuta

Preprint

In the authors' words

This paper presents the first systematic study of $[F]$ -irregular graphs, a concept that parallels classical $F$ -irregularity. For a fixed graph $F$ , a graph $G$ is $[F]$ -irregular if the numbers of its induced subgraphs isomorphic to $F$ containing a given vertex are pairwise distinct for all vertices of $G$ . We prove that there exist infinitely many $[P_{n}]$ -irregular graphs for any path $P_{n}$ of order $n \geq 3$ . We establish that a non-trivial $[P_{3}]$ -irregular graph of order $k$ exists if and only if $k \geq 7$ . Finally, we propose the Strong Conjecture on $[F]$ -irregular graphs.

Main resultLimitation the authors admit

Read the paper PDF

Appeared: Tuesday, September 22. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 20 pages, 6 figures

On infinite families of [Pn​]-irregular graphs

In the authors' words

More on Combinatorics & discrete math that day

Circular s-choice parking functions: an exact closed formula via rotational symmetry

Single-Fragment Forensic Coding via Multidimensional Cyclically Permutable Codes

The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach

Proof of Almkvist's conjecture on the unimodality of partition polynomials

The Last Seven Open Radii for Perfect Codes in the Johnson Scheme

On infinite families of $[P_{n}]$ -irregular graphs