RUS  ENG
Full version
JOURNALS // Algebra and Discrete Mathematics // Archive

Algebra Discrete Math., 2014 Volume 18, Issue 1, Pages 97–108 (Mi adm484)

This article is cited in 1 paper

RESEARCH ARTICLE

On graphs with graphic imbalance sequences

Sergiy Kozerenko, Volodymyr Skochko

Department of Mechanics and Mathematics, Kyiv National Taras Shevchenko Univ., Volodymyrska str., 64, 01033 Kyiv, Ukraine

Abstract: The imbalance of the edge $e=uv$ in a graph $G$ is the value $imb\,_{G}(e)=|d_{G}(u)-d_{G}(v)|$. We prove that the sequence $M_{G}$ of all edge imbalances in $G$ is graphic for several classes of graphs including trees, graphs in which all non-leaf vertices form a clique and the so-called complete extensions of paths, cycles and complete graphs. Also, we formulate two interesting conjectures related to graphicality of $M_{G}$.

Keywords: edge imbalance, graph irregularity, graphic sequence.

MSC: 05C07, 05C99

Received: 14.05.2014
Revised: 14.05.2014

Language: English



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024