On the Irregularity of $$\pi $$-Permutation Graphs, Fibonacci Cubes, and Trees

Autor:	Sandi Klavžar, Yaser Alizadeh, Emeric Deutsch
Rok vydání:	2020
Předmět:	Mathematics::Combinatorics Fibonacci cube General Mathematics 010102 general mathematics 01 natural sciences Upper and lower bounds Graph 010101 applied mathematics Combinatorics Permutation Exact formula Pi 0101 mathematics Invariant (mathematics) MathematicsofComputing_DISCRETEMATHEMATICS Mathematics
Zdroj:	Bulletin of the Malaysian Mathematical Sciences Society. 43:4443-4456
ISSN:	2180-4206 0126-6705
DOI:	10.1007/s40840-020-00932-9
Popis:	The irregularity of a graph G is the sum of $$|\mathrm{deg}(u) - \mathrm{deg}(v)|$$ over all edges uv of G. In this paper, this invariant is considered on $$\pi $$ -permutation graphs, Fibonacci cubes, and trees. An upper bound on the irregularity of $$\pi $$ -permutations graphs is given, and $$\pi $$ -permutation graphs that attain the equality are characterized. The concept of the irregularity is extended to arbitrary edge subsets and applied to permutation edges of $$\pi $$ -permutation graphs. An exact formula for the irregularity of Fibonacci cubes is proved. An upper bound on the irregularity of trees in terms of the diameter is given, and trees that attain the equality are characterized.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::10094234149419658c28eec67b1a284e https://doi.org/10.1007/s40840-020-00932-9 Zobrazit plný text záznamu Plný text ve formátu PDF Plný text ve formátu HTML
Nepřihlášeným uživatelům se plný text nezobrazuje	K zobrazení výsledku je třeba se přihlásit.