Extremizing antiregular graphs by modifying total σ \sigma -irregularity

Martin Knor, Riste Škrekovski, Slobodan Filipovski, Darko Dimitrov, [0.1cm] Faculty of Information Studies in Novo Mesto, Slovenia, [0.1cm] FAMNIT, University of Primorska, Koper, Slovenia · 2024

Read Extremizing antiregular graphs by modifying total σ \sigma -irregularity by Martin Knor, Riste Škrekovski, Slobodan Filipovski, Darko Dimitrov, [0.1cm] Faculty of Information Studies in Novo Mesto, Slovenia, [0.1cm] FAMNIT, University of Primorska, Koper, Slovenia (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-01530.txt.

Description

Abstract The total σ \sigma -irregularity is given by σ t ​ ( G ) = ∑ { u , v } ⊆ V ⁡ ( G ) ( d G ​ ( u ) − d G ​ ( v ) ) 2 , \sigma_{t}(G)=\sum_{\{u,v\}\subseteq V(G)}\left(d_{G}(u)-d_{G}(v)\right)^{2}, where d G ​ ( z ) d_{G}(z) indicates the degree of a

Catalog record

CREATORMartin Knor, Riste Škrekovski, Slobodan Filipovski, Darko Dimitrov, [0.1cm] Faculty of Information Studies in Novo Mesto, Slovenia, [0.1cm] FAMNIT, University of Primorska, Koper, Slovenia
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE25 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2411-01530

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Extremizing antiregular graphs by modifying total σ \sigma -irregularity Martin Knor, Riste Škrekovski, Slobodan Filipovski, Darko Dimitrov, [0.1cm] Faculty of Information Studies in Novo Mesto, Slovenia, [0.1cm] FAMNIT, University of Primorska, Koper, Slovenia Abstract The total σ \sigma -irregularity is given by σ t ​ ( G ) = ∑ { u , v } ⊆ V ⁡ ( G ) ( d G ​ ( u ) − d G ​ ( v ) ) 2 , \sigma_{t}(G)=\sum_{\{u,v\}\subseteq V(G)}\left(d_{G}(u)-d_{G}(v)\right)^{2}, where d G ​ ( z ) d_{G}(z) indicates the degree of a vertex z z within the graph G G . It is known that the graphs maximizing σ t \sigma_{t} -irregularity are split graphs with only a few distinct degrees. Since one might typically expect that graphs with as many distinct degrees as possible achieve maximum irregularity measures, we modify this invariant to σ t f ⁡ ( n ) ​ ( G ) = ∑ { u , v } ⊆ V ⁡ ( G ) | d G ​ ( u ) − d G ​ ( v ) | f ⁡ ( n ) , \sigma_{t}^{f(n)}(G)=\sum_{\{u,v\}\subseteq V(G)}|d_{G}(u)-d_{G}(v)|^{f(n)}, where n = | V ⁡ ( G ) | n=|V(G)| and f ⁡ ( n ) > 0 f(n)>0 . We study under what conditions the above modification obtains its maximum for antiregular graphs. We consider general graphs, trees, and chemical graphs, and accompany our results with a few problems and conjectures. 1 Introduction and preliminaries We restrict our study to undirected graphs with a finite number of vertices, excluding any graphs that have loops or parallel edges. For any terminology or notation not explicitly defined herein, we direct the reader to the comprehensive textbook by Bondy and Murty [ 8 ] . The degree of a vertex v in a graph G , d_{G}(v) , is defined as the number of edges incident to that vertex. A graph G is labeled regular when every vertex has the identical degree; conversely, it is labeled irregular . An invariant of the graph G , symbolized by I(G) , is referred to as an irregularity metric or index of irregularity if it meets the conditions I(G)\geq 0 and I(G)=0 exclusively when the graph G is regular. In this study, we delve into irregularity measures of graphs, focusing on differences between pairs of vertices within a graph. Let G have n vertices. For any vertex v\in V(G) , its degree d_{G}(v) satisfies 0\leq d_{G}(v)\leq n-1 . If d_{G}(v)=n-1 , it implies that all other vertices have positive degrees, ensuring that no vertex is isolated. Consequently, there cannot exist a graph where all vertices have distinct degrees. The most favorable scenario in this context is to have n-1 distinct degrees, with one degree repeated. Graphs with such configurations are referred to by various names, with the most widely recognized term being antiregular. Notably, there exist precisely two antiregular graphs on n vertices, with one being the complement of the other. As one of these graphs exhibits vertices with degrees ranging from 0 to n-2 , it naturally consists of disconnected components. Consequently, there exists only one connected antiregular graph on n vertices. This specific graph features vertices with degrees ranging from 1 to n-1 , with the degree \lfloor\frac{n}{2}\rfloor occurring twice [ 7 ] . For further exploration of properties and findings related to antiregular graphs, interested readers are directed to the survey by Ali [ 3 ] . The imbalance of an edge e=uv\in E is defined as {{\rm imb}}(e)=\left|d_{G}(u)-d_{G}(v)\right| . In [ 6 ] , Albertson defined the irregularity of G as sum of imbalances of all edges of a graph, i.e., \displaystyle{{\rm irr}}(G)=\sum_{e\in E(G)}{{\rm imb}}(e)=\sum_{uv\in E(G)}|d_{G}(u)-d_{G}(v)|. (1) Another irregularity measure introduced in [ 1 ] is closely connected to ( 1 ). Similar to ( 1 ), this measure also quantifies the irregularity of a graph solely based on the differences in the degrees of its vertices. For a given graph G , it is expressed as: \displaystyle{\rm irr}_{t}(G)=\sum_{\{u,v\}\subseteq V(G)}\left|d_{G}(u)-d_{G}(v)\right|. (2) Due to its evident relationship with the irregularity measure {\rm irr}(G) , the invariant {\rm irr}_{t}(G) is commonly referred to as the total irregularity of a graph. The total irregularity of a graph is solely determined by its degree sequence, making it an effective measure even when vertex adjacency details are unavailable. Notably, there are graphs exhibiting high irr despite having very limited degree diversity, a characteristic unexpected in highly irregular graphs. Conversely, as demonstrated in [ 1 ] , graphs with maximal {\rm irr_{t}} exhibit large degree sets, with some even possessing the largest possible ones. A comparison between irregularity and total irregularity was presented in [ 10 ] . An alternative to the Albertson irregularity index, aiming to avoid the absolute value calculation, led to the introduction of the irregularity index {\sigma}(G) in [ 14 ] . It is defined as follows: \displaystyle{\sigma}(G) \displaystyle= \displaystyle\sum_{uv\in E(G)}(d_{G}(u)-d_{G}(v))^{2}. Graphs with maximal \sigma -irregularity have been characterized in [ 2 ] , where lower bounds on \sigma -irregularity were also established. The inverse problem, which involves determining the existence of a graph with \sigma -irregularity equal to a given non-negative integer, was addressed in [ 14 , 2 ] . Réti [ 16 ] further explored \sigma -irregularity in comparison with various well-known irregularity measures across certain classes of graphs. A connected graph is termed k -cyclic if it consists of n vertices and n+k-1 edges. In [ 5 ] , the study determined connected k -cyclic graphs exhibiting maximal \sigma -irregularity. If a sequence \mathcal{D}=(d_{1},d_{2},\ldots,d_{n}) corresponds to the degrees of vertices in some graph, it is called graphical . Such a sequence, when arranged in non-increasing order with d_{1}\geq d_{2}\geq\cdots\geq d_{n} , is referred to as a degree sequence . The characterization of extremal graphs, concerning \sigma -irregularity, with a given degree sequence was recently undertaken in [ 9 ] . To establish that a given sequence of non-negative integers represents the degree sequence of some graph, one can utilize the following characterization by Erdős and Gallai [ 12 ] . Theorem 1 . For any integer n\geq 1 and non-increasing sequence d_{1}\geq d_{2}\geq\dots\geq d_{n} , there exists a graph with n vertices having the respective degrees d_{1},d_{2},\dots,d_{n} if and only if two conditions are satisfied: 1. \sum_{i=1}^{n}d_{i} is even; 2. For all 1\leq k\leq n-1 , the inequality d_{1}+d_{2}+\dots+d_{k}\leq k(k-1)+\sum\limits_{i=k+1}^{n}\min(k,d_{i}) holds. A connected graph with maximum degree at most 4 is commonly referred to as a chemical graph , while a non-cyclic chemical graph is denoted as a chemical tree . In [ 2 ] , it was established that among the chemical trees explored, the path graph exhibits the smallest \sigma -irregularity. Additionally, [ 15 ] provided a characterization of chemical trees with maximal \sigma -irregularity. The graphs with the same degree sequence do not necessarily have the same \sigma -irregularity (see Figure 1 from [ 11 ] for an example). Figure 1: Illustration of two distinct graphs, G_{1} and G_{2} , which share the degree sequence 1,1,1,2,2,2,3 . Despite their differing irregularity values ( {\rm irr}(G_{1})=10 and {\rm irr}(G_{2})=8 ), they exhibit identical total irregularity ( {\rm irr}_{t}(G_{1})={\rm irr}_{t}(G_{2})=22 ). To avoid this, a

Read the complete text