# Advances in Domination Irregularity and Chromatic Properties of Graphs and Digraphs

Duaa Abdullah

► To cite this version:

Duaa Abdullah. Advances in Domination Irregularity and Chromatic Properties of Graphs and Digraphs. 2025. hal-05381336

HAL Id: hal-05381336

https://hal.science/hal-05381336v1

Preprint submitted on 25 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Advances in Domination Irregularity and Chromatic Properties of Graphs and Digraphs

Duaa Abdullah*

Moscow Institute of Physics and Technology

## Abstract

A substantial portion is devoted to chromatic properties of distance graphs in $\mathbb{R}^n$. By refining and generalising the Frankl-Wilson and Raigorodskii constructions, we demonstrate that chromatic numbers of order at least $(1.207... + o(1))^n$ can be achieved without adhering to the classical parameter choice $l \sim \frac{2-\sqrt{2}}{2}n$, thereby confirming that the specific coordinate structure previously assumed is not necessary for near-optimal exponential lower bounds on $\chi(\mathbb{R}^n)$.

Further results concern spectral spreads of line graphs (Laplacian and signless Laplacian), extremal Harary indices in bipartite graphs with prescribed matching number, and a detailed analysis of graph irregularity measures. Majorisation principles linking degree sequences to total irregularity are emphasised, and asymptotic sizes of maximal and minimal irregular oriented graphs are clarified.

**MS Classification 2020:** 05C05, 05C12, 05C20, 05C25, 05C35, 05C76, 52C20, 68R10.

**Keywords:** Domination number, Distance graphs, Chromatic number of $\mathbb{R}^n$, Extremal graph theory, Spectral graph theory

## 1 Introduction

Given a simple undirected graph $G$, let $V(G)$ denote its vertex set containing $n$ vertices, and $E(G)$ its edge set containing $m$ edges. Such a graph is referred to as an $(n, m)$ graph [2, 11]. Once vertices are labeled, each vertex is identified by its label, and an edge connecting vertices $i$ and $j$ is represented by $ij$. The degree of vertex $i$ is denoted by $d_G(i)$. The graph $G$ is called $r$-regular if every vertex has degree $r$. For any finite set $U$, its cardinality is $|U|$. When $U \subseteq V(G)$, the notation $G - U$ indicates the subgraph induced by the vertex set $V(G) \setminus U$. The diameter of $G$, denoted $\text{diam}(G)$, is the greatest distance between any pair of vertices in $G$ (see equation (16)). For two graphs $G_1$ and $G_2$ with disjoint vertex sets, their join, denoted $G_1 \vee G_2$, is the graph formed by taking their union and adding edges between every vertex of $G_1$ and every vertex of $G_2$.

In 1961 Erdős and Hajnal established the first upper bound (see [3, 24]) for $m(n)$ as

$$m(n) \le \binom{2n-1}{n} = (4 + o(1))^n.$$

This bound holds for the family of all $n$-element subsets of a $(2n-1)$-element set. Erdős provided the first non-trivial estimates for $m(n)$ in 1963, as stated in Theorem 2.4. Concerning matrix representations of a graph $G$, the adjacency matrix is denoted by $A(G)$. The Laplacian matrix is defined by $L(G) = D(G) - A(G)$, where $D(G)$ is the degree matrix, a diagonal matrix with vertex degrees on the diagonal. The signless Laplacian matrix is defined as $Q(G) = D(G) + A(G)$. The eigenvalues of $A(G)$, called the eigenvalues of the graph $G$, are denoted by $\lambda_i = \lambda_i(G)$.

A simple bipartite graph $G = (V_1, V_2, E)$ consists of two disjoint vertex sets, $V_1$ and $V_2$, where edges $E$ connect only vertices from different sets. This guarantees that no edge links vertices within

<footnote>*Corresponding Author: duaa1992abdullah@gmail.com</footnote>
the same partition [5]. When every vertex in $V_1$ is connected to every vertex in $V_2$, the bipartite graph is called complete and denoted by $K_{a,b}$, where $a = |V_1|$ and $b = |V_2|$. The distance-based graph invariants, the Wiener index $W(G)$ and the Harary index $H(G)$, are defined as follows:

$$W(G) = \sum_{\{u,v\} \subseteq V(G)} d_G(u, v), \quad H(G) = \sum_{\{u,v\} \subseteq V(G)} \frac{1}{d_G(u, v)}.$$

A pair $H = (V, E)$ is a hypergraph [6] if $V$ is a finite set of vertices and $E \subseteq 2^V$ is a set of hyperedges, with the assumption that each vertex is incident to at least one edge. A hypergraph is called n-uniform if all edges have cardinality $n$. Thus, any graph is a 2-uniform hypergraph. Sometimes such hypergraphs are referred to simply as n-graphs [6]. An r-colouring of a hypergraph is a mapping $f: V \to \{1, \dots, r\}$. The colouring is proper if every edge $e \in E$ contains vertices $v_1, v_2 \in e$ such that $f(v_1) \neq f(v_2)$. The chromatic number of $H$ is the smallest $r$ for which a proper $r$-colouring exists.

M. K. Baca et al. [7] introduced edge labelings of a graph $G$ with positive integers such that the sums of labels on edges incident to each vertex are distinct. These labelings are called irregular assignments. The irregularity strength of $G$, denoted by $irr_s(G)$, is the smallest integer $k$ for which $G$ admits an irregular assignment using labels from $\{1, 2, \dots, k\}$. A lower bound for $irr_s(G)$ is given by

$$irr_s(G) \geq \max_{1 \leq i \leq \Delta} \left\{ \frac{n_i + i - 1}{i} \right\},$$

where $n_i$ is the number of vertices of degree $i$ and $\Delta$ is the maximum degree of $G$. The total irregularity of $G$, denoted $irr_t(G)$, is defined as

$$irr_t(G) = \sum_{u,v \in V(G)} |d(u) - d(v)|,$$

which measures the overall deviation from degree regularity in $G$. This measure relates to classical irregularity indices such as the Albertson index and the total irregularity of line graphs. Recent work [1] established sharp upper and lower bounds on the total irregularity of line and total graphs, expressed in terms of the order and maximum degree of the original graph. Further extensions to graph products and operations appear in [9] and [10], providing a comprehensive framework for analyzing irregularity propagation under standard graph transformations.

The chromatic number $\chi(\mathbb{R}^n)$ of the n-dimensional Euclidean space $\mathbb{R}^n$ is the minimum number of colors needed to color every point in $\mathbb{R}^n$ such that no two points exactly one unit apart share the same color [24]. Notably, the exact value of the chromatic number in two dimensions remains unknown. The currently best known bounds are $4 \leq \chi(\mathbb{R}^2) \leq 7$. This problem has been extensively studied for decades and is a fundamental question in combinatorial geometry, leading to many profound results. Despite its popularity, it remains highly challenging and unresolved [28].

A graph $G$ is called k-regular if every vertex $a$ has exactly $k$ neighbors in its neighborhood $[a]$. The graph $G$ is an edge-regular graph with parameters $(v, k, \lambda)$ if it has $v$ vertices, is k-regular, and every edge lies in exactly $\lambda$ triangles [26]. More specifically, $G$ is strongly regular with parameters $(v, k, \lambda, \mu)$ if it is edge-regular and, additionally, for any two vertices $a$ and $b$ at distance two, the intersection $[a] \cap [b]$ contains exactly $\mu$ vertices [25]. When the diameter of such a graph is two, it is referred to simply as a strongly regular graph.

The graph $G$ is called strongly $(\lambda, \mu)$-regular if every edge belongs to exactly $\lambda$ triangles and for every pair of vertices $a, b$ with distance $d(a, b) = 2$, their neighborhoods intersect in exactly $\mu$ vertices. For any edge or vertex pair, the number of common neighbors $|[a] \cap [b]|$ is denoted by $\lambda(a, b)$ if $d(a, b) = 1$, and by $\mu(a, b)$ if $d(a, b) = 2$. A sequence $\mathcal{D} = (d_1, d_2, \dots, d_n)$ representing the degrees of vertices in a graph is called a graphical sequence. When its terms are sorted in non-increasing order, $d_1 \geq d_2 \geq \dots \geq d_n$, or in non-decreasing order, $d_1 \leq d_2 \leq \dots \leq d_n$, it is called a degree sequence.

In the 1950s, E. Nelson posed the problem of determining the minimal number $\chi(\mathbb{R}^n)$ of colors needed to color the points of the Euclidean space $\mathbb{R}^n$ such that no two points at unit distance share
the same color (see [28]). This quantity, known as the chromatic number of the space, was further studied by H. Hadwiger (see [29]), who investigated related questions as early as 1944 (see [30]), and attracted the attention of P. Erdős, noted for his interest in such problems. The term "chromatic number" is intentional and fits naturally within graph theory. The Nelson–Erdős–Hadwiger problem can be reframed so that

$$ \chi(\mathbb{R}^n) = \chi(\mathcal{G}_n), $$

where $\mathcal{G}_n = (\mathcal{V}_n, \mathcal{E}_n)$ is the infinite graph with vertex set

Nevertheless, a fundamental result by P. Erdős and N. de Bruijn offers a key insight: if a graph has a finite chromatic number, this value is attained by some finite subgraph [31]. Thus, establishing that $\chi(\mathbb{R}^n)$ is finite allows one to focus on finite subgraphs of $\mathcal{G}_n$, known as finite distance graphs. For instance, it is straightforward to verify that $\chi(\mathbb{R}^n) \le (cn)^n$ for some constant $c > 0$, confirming the finiteness of the chromatic number. Moreover, it has been shown that $\chi(\mathbb{R}^n) \le (3 + o(1))^n$ [32]. The exponential growth of these bounds was first demonstrated by P. Frankl and R. M. Wilson [33], who proved in 1981 that

$$ \chi(\mathbb{R}^n) \ge (1.207 \dots + o(1))^n. $$

The only enhancement to the Frankl–Wilson theorem was established by Raigorodsky [34], yielding

$$ \chi(\mathbb{R}^n) \ge (1.239 \dots + o(1))^n. $$

The simplest distance graphs that produce the lower bound $\chi(\mathbb{R}^n) \ge (1.207 \dots + o(1))^n$ obtained by Frankl and Wilson [33] still have unresolved aspects. These graphs are of the form $G = (V, E)$, where

$$ V \subseteq \Sigma = \{x = (x_1, \dots, x_n) : x_i \in \{0, 1\}, |\{i : x_i = 1\}| = l\} $$

for some $l \in [0, n]$, and

$$ E = \{(x, y) \in V \times V : |x - y| = a\}, $$

with parameters $l$ and $a$ chosen arbitrarily. Formally, $G$ is not required to be a subgraph of $\mathcal{G}_n$, since edges in $\mathcal{G}_n$ correspond to pairs at unit distance rather than distance $a$. However, the chromatic number of $\mathbb{R}^n$ is invariant under scaling of the forbidden distance (i.e., the distance prohibited between vertices of the same color), so the choice of unit distance in the original definition of $\mathcal{G}_n$ is purely conventional.

## 2 Preliminaries

Let $\prod = (s_1, s_2, \dots, s_k)$ be the ordered partition [13] of $V(G)$. so that, we have: $r(u(\prod)) = (d(u, S_1), \dots, d(u, S_k))$. The set $S_i$ is called resolves $u, w \in V(G)$, if $d(u, S_i) \ne d(w, S_i)$. The partition dimension $\beta_p(G)$ of $G$ is the minimum cardinality of a resolving partition of $G$. For a fuzzy graph:

$$ \delta(G) = \bigwedge \left\{ \frac{d(v)}{v} \forall v \in V \right\}, \quad \Delta(G) = \bigvee \left\{ \frac{d(v)}{v} \forall v \in V \right\}. $$

If the geometric [17] representation of a graph on that surface is such that no two of its edges intersect each other. A planar is a graph G drawn in plane with any two of its edges intersecting. A subset $D$ of $V(G)$ is a dominating set in $G$ if every vertex in $V(G) \setminus D$ has at least one neighbor in $D$. The domination number $\gamma(G)$ is the minimum cardinality of such dominating sets [19]. A dominating set of size $\gamma(G)$ is called a $\gamma(G)$-set. A vertex $v \in V(G)$ is $\gamma(G)$-critical if $\gamma(G - v) \le \gamma(G)$. For a graph $G = (V, E)$, subdividing an edge $e = uv \in E$ by introducing a vertex $x$ results in a graph with vertex set $V \cup \{x\}$ and edge set $(E \setminus \{uv\}) \cup \{ux, xv\}$. Let $G_{e_1, e_2, \dots, e_k}$ denote the graph obtained by subdividing each edge $e_1, e_2, \dots, e_k$ once. Also, let $G_{e, k}$ denote the graph formed by subdividing edge $e$ with $k$ vertices, replacing the edge $e = uv$ with the path $(u, x_1, x_2, \dots, x_k, v)$. Subdivision numbers are considered only for connected graphs of order at least 3, since for the graph $K_2$, subdividing its unique edge does not increase the domination number.
**Definition 1** ([17]). Let $\xi: (V, \sigma, \mu)$ be a fuzzy graph. A subset $D$ of $V$ is said to be a dominating set of $G$ if for every $v \in V$ there exists an element $u \in D$ such that $\mu(u, v) = \sigma(u) \wedge \sigma(v)$. A dominating set $D$ of $G$ is called minimal dominating set of $G$ if every node $v \in D$, $D\{v\}$ is not a dominating set. The domination number and it is denoted by $\gamma(G)$.

Let $G$ be fuzzy planar graph with planarity value $f$, where $f = \frac{1}{1 + \{I_{P_1} + I_{P_2} + \dots + I_{P_n}\}}$. The range of $f$ is $0 < f \le 1$. Here $P_1, P_2, \dots, P_n$ be the points of intersections between the edges. In a graph $G = (V, \sigma, \mu)$, $E$ contains two edges $\mu(a, b)$ and $\mu(c, d)$, which are intersected at a point $P$. Strength of the fuzzy edge $I_{(a,b)} = \frac{\mu(a,b)}{\{\sigma(a) \wedge \sigma(b)\}}$. The intersecting point at $p$ is $I_p = \frac{I_{(a,b)} + I_{(c,d)}}{2}$.

**Definition 2** ([17]). If a graph $G$ is said to be domination in fuzzy planar graph if i. $G = (V, \sigma, \mu)$ be a fuzzy planar graph with planarity value $f$. ii. Let $x, y \in V$, $x$ dominates $y$ in $G$ then $\mu(x, y) \le \mu(x) \wedge \sigma(y)$ iii. A subset $D$ of $V$ is called a dominating set in $G$ if for every $y$ not belonging to $D$, there exist $x \in D$ such that $x$ dominates $y$. iv. The minimum fuzzy cardinality of a dominating set in $G$ is called the dominating number of $G$ and is denoted by $\gamma_{FP}$.

**Definition 3** ([1]). The first Zagreb index of $G$, $M_1(G)$, is defined as

$$M_1(G) = \sum_{i \in V(G)} d^2(i).$$

**Definition 4** ([6]). An ordered pair of edges is called a 2-chain if these edges have exactly one vertex in common. A 2-chain $(e_1, e_2)$ is said to be ordered according to the order $\pi$ if $\pi(v_1) \le \pi(v_2)$ for any two vertices $v_1 \in e_1, v_2 \in e_2$.

Since $\Delta^-(C_m \square C_n) = \Delta^-(C_m \square P_n) = \Delta^-(C_m \square P_n) = \Delta^-(P_m \square C_n) = 2$ then $\gamma_k(C_m \square C_n) = \gamma_k(P_m \square P_n) = \gamma_k(C_m \square P_n) = \gamma_k(P_m \square C_n) = mn$ for $k \ge 3$. The remained case is $k = 2$. Let $S$ be a 2-dominating set of $C_m \square C_B, P_m \square P_n, C_m \square P_n$ or $P_m \square C_n$. If a vertex $(i, j) \notin S$, then

$$\{(i-1, j), (i, j-1)\} \subset S.$$

This implies that $|K_j \cap S| \ge \lfloor m/2 \rfloor$ for all $j = 1, 2, \dots, n$ and $|R_i \cap S| \ge \lfloor n/2 \rfloor$ for all $i = 1, 2, \dots, m$.

**Lemma 2.1** ([1]). Let $G$ be an $(n, m)$ graph with $m \ge 1$ edges. Let $q_i$ be the $i$-th greatest signless Laplacian eigenvalue of $G$ and $\lambda_i(\mathcal{L}(G))$ the $i$-th greatest eigenvalue of its line graph $\mathcal{L}(G)$. Then

$$q_i = \lambda_i(\mathcal{L}(G)) + 2, \qquad (1)$$

for $i = 1, 2, \dots, k$, where $k = \min\{n, m\}$. In addition, if $m > n$, then $\lambda_i(\mathcal{L}(G)) = -2$ for $i \ge n+1$ and if $n > m$, then $q_i = 0$ for $i \ge m+1$.

If $G$ is a graph with $m$ edges, it is a simple exercise to verify that the number of edges of $\mathcal{L}(G)$ is given by $\sum_{i \in V(G)} \frac{d(i)(d(i)-1)}{2}$ and then, the number of edges of $\mathcal{L}(G)$ can be given by

$$m_{\mathcal{L}(G)} = \frac{M_1(G)}{2} - m. \qquad (2)$$

**Lemma 2.2** ([1]). Let $G$ be an $(n, m)$ graph. Then $\text{irr}_s(G) \le \lambda_1 + \sqrt{2m - \lambda_1^2} \le 2\sqrt{m}$.

The maximum cardinality [14] of a matching of $G$ is denoted by $\alpha'(G)$ (abbreviated $\alpha'$). The join $G_1 \vee G_2$ is obtained from the two graphs $G_1$ and $G_2$ by adding all the edges between $V(G_1)$ and $V(G_2)$.

**Theorem 2.3** ([14]). For every simple connected graph $G$ of order $n \ge 3$ different from $K_4$, $sd_{\gamma_t}(G) \le \lfloor \frac{2n}{3} \rfloor$ with equality if and only if $G$ is isomorphic to $P_3, K_3, K_{1,3}, K_{1,3} + e, K_4 - e, K_5 - e, K_5$. If $\delta \le k, n \ge 2$ for some $k \in \mathbb{N}$ then we have: $\alpha'(G) \ge k$.
For any graph $G$ with a strong support vertex $sd_{\gamma_t}(G) \le 2$. Then, we can write summarize as:
$$sd_{\gamma_t}(G): \begin{cases} sd_{\gamma_t}(G) = 1 & \text{two adjacent support vertices.} \\ 1 \le sd_{\gamma_t}(G) \le 3 & \text{two adjacent support vertices.} \\ sd_{\gamma_t}(G) = 1 & \gamma_t(G) = 3, 2, n \ge 3 \\ sd_{\gamma_t}(G) \le n - \gamma_t(G) + 1 & n \ge 3 \end{cases}$$

**Theorem 2.4 ([6]).** For any $n \ge 2$,

$$2^{n-1} \le m(n) \le (1 + o(1)) \frac{e \log 2}{4} n^2 \cdot 2^n. \quad (3)$$

The quantity $m_l(n, r)$ defined as the minimum number of edges in a hypergraph $H$ satisfying the condition $ch(H) > r$. It is clear that $m_l(n, r) \le m(n, r)$. Let us turn to lower estimates $m_l(n, r)$ for $m_l(2, r) = m(2, r) = \binom{r+1}{2}$, since the degree of each vertex should be at least $r$ (and, hence, there should be at least $r+1$ vertices). According to Definition 4 and Theorem 2.4 from (3) we find that

$$m(n, r) \le \binom{rn}{n} \frac{\log(n)}{\log(n) - 1} \cdot \frac{1}{\left[\frac{n}{\log(n)}\right]}, \quad m(n, r) \le cn^2 (\log n) \left(\frac{3e}{4}\right)^n \cdot r^n. \quad (4)$$

The total sum of the degrees of the vertices $v_i$ we count each edge at most $n$ times, which immediately implies that:

$$s(n, r) \ge \frac{[d(n - 1, r)]^2}{n^3}.$$

Which gives the estimate:

$$s(n, r) \ge \frac{[d(n - 1, r)]^2}{n^2}.$$

**Theorem 2.5 ([13]).** For any graph $G$ of order $n \ge 3$, $\beta_p(G) \le \eta_p(G) \le \beta_p(G) + 1$. Then, every locating coloring of $G$ is also a resolving dominating partition of $G$.

During this study of the Sigma index, we deviate from the traditional definition and adopt the formula derived from Theorem 2.6, which is expressed in terms of the degree sequence $\mathcal{D}$.

**Theorem 2.6 ([22, 23]).** Let $T$ be a tree of order $n$, and let $\mathcal{D} = (d_1, \dots, d_n)$ be a degree sequence such that $d_n \ge \dots \ge d_1$. Then, the Sigma index of the tree $T$ is given by:

$$\sigma(T) = \sum_{i \in \{1, n\}} (d_i + 1)(d_i - 1)^2 + \sum_{i=2}^{n-1} (d_i + 2)(d_i - 1)^2 + \sum_{i=2}^{n-1} (d_i - d_{i+1})^2 + 2n - 2.$$

# 3 Main Result

We established that a fuzzy graph (f-graph) is defined as a triplet $\zeta = (V, \sigma, \mu)$, where $V$ is the vertex set, $\sigma$ is a fuzzy subset of $V$, and $\mu$ is a fuzzy relation on $\sigma$ such that for all $u, v \in V$, $\mu(u, v) \le \sigma(u) \lor \sigma(v)$. A fuzzy graph $H = (V, \tau)$ is called a partial fuzzy subgraph of $G = (V, \sigma, \mu)$ if $\tau(u) \le \sigma(u)$ for all $u \in V$. The sum of membership values in $V$ is given by $\sum_{x \in V} \sigma(x)$.

## 3.1 On Domination Number

The $k$-domination number of the Cartesian products of two directed cycles $C_m$ and $C_n$, two directed paths $P_m$ and $P_n$, and mixed products $C_m \square P_n$ and $P_m \square C_n$ for arbitrary $m$ and $n$ has been studied. Note the identity:

$$\lfloor n/2 \rfloor + \lfloor (n-1)/2 \rfloor = n-1.$$

In a 1-regular digraph $D$ with $n$ vertices, every vertex belongs to a 2-dominating set of $D$, hence $\gamma_2(D) = n$. Specifically, $\gamma_2(C_n) = n$. Furthermore, every $k$-dominating set of a digraph $D$ must include any vertex with indegree at most $k-1$.
The label of a vertex $v$, also known as its status [19] and denoted by $sta(v)$, is fundamental in defining two graph operations on $G$. Operation $T_1$ occurs when $sta(v) = A$: it adds a path $(x, y, z)$, connects $v$ to $x$, and assigns statuses $sta(x) = sta(y) = B$ and $sta(z) = A$. Operation $T_2$ applies when $sta(v) = B$: it adds a path $(x, y)$, connects $v$ to $x$, and sets $sta(x) = B$ and $sta(y) = A$. The family $T$ consists of trees derived from the path $P_4$—where the two leaves are labeled $A$ and the two support vertices are labeled $B$—through a finite sequence of $T_1$ and $T_2$ operations. For any $T \in T$, let $A(T)$ and $B(T)$ denote the vertex sets with statuses $A$ and $B$, respectively. The following corollary holds for any $G \in F_0$ and vertex $v \in V(G)$: (1) if $v$ is a leaf, then $sta(v) = A$; (2) if $v$ is a support vertex, then $sta(v) = B$; (3) if $G \in A \cup B$ and $sta(v) = A$, then $N(v) \subseteq B(G)$; (4) if $sta(v) = B$, then $v$ is adjacent to exactly one vertex in $A(G)$ and at least one vertex in $B(G)$; (5) for any $x, y \in A(G)$, the distance $d(x, y) \ge 3$; and (6) $A(G)$ forms a total dominating set $\gamma_t$. Moreover, for $G \in F_0$ and $x \in A(G)$, we have $\gamma(G - x) \le \gamma(G)$. For a graph $G$ containing a path $P_3 = (w, y, z)$ with degrees $d_G(z) = 1$ and $d_G(y) = d_G(w) = 2$, it follows that

$$ \gamma(G - \{w, y, z\}) = \gamma(G) - 1. $$

A unicyclic graph $G$ satisfies $msd(G) = 3$ if and only if $G$ belongs to the family $F$. For a graph $G$ with a path $P_5 = (w_1, w_2, w_3, z_2, z_1)$, where $d_G(w_1) = d_G(z_1) = 1$, $d_G(w_2) = d_G(z_2) = 2$, and $d_G(w_3) \ge 3$, we have

$$ \gamma(G - \{w_1, w_2\}) = \gamma(G) - 1. $$

Therefore, for any connected graph $G$ with order $n \ge 3$ and minimum degree $\delta(G) = 1$, the inequality

$$ sd_{\gamma_t}(G) \le \alpha'(G) + 1 $$

holds, where

$$ \alpha'(G) = |s| + \sum_{i=1}^{l} \frac{n_i - 1}{2}. $$

The relation between the $k$-domination and $k$-independence numbers was established [20] for any graph $G$ as $\gamma_k(G) \le \beta_k(G)$. The relationship between the 2-domination and independence numbers states that for any tree $T$, $\beta(T) \le \gamma_2(T) \le \frac{3}{2}\beta(T)$. The following observation [20] holds: Let $G$ be a graph and $k \ge 1$ an integer. If a vertex $v$ satisfies $d(v) \ge k-1$, then $v$ belongs to every independent $k$-dominating set of $G$. If $d(v) = t \ge k$ and the neighborhood of $v$ contains fewer than $k$ independent vertices, then $v$ also belongs to every independent $k$-dominating set of $G$. Additionally, (1) for any $k > 1$, there exist graphs with no independent $k$-dominating set; (2) if $G$ has two adjacent vertices each with degree at most $k-1$, then $G$ has no independent $k$-dominating set. Let $T$ be a 2-tree of order $n \ge 6$ with an independent 3-dominating set $S$, then

$$ \frac{n+1}{2} \le |S| \le n-2. $$

For any $u, v \in V(D)$, the arc from $u$ to $v$ is denoted by $(u, v)$. The vertices $u$ and $v$ are said to be adjacent if $(u, v)$ is an arc [21]. For a subset $S \subseteq V(D)$ and a vertex $v \in V(D)$, define

$$ N_S^-(v) = \{u \in S \mid (u, v) \in A(D)\} \quad \text{and} \quad N_S^+(v) = \{u \in S \mid (v, u) \in A(D)\}. $$

The in-degree and out-degree of $v$ with respect to $S$ are

$$ \deg_S^-(v) = |N_S^-(v)| \quad \text{and} \quad \deg_S^+(v) = |N_S^+(v)|, $$

respectively. Also define

$$ N_S^-[v] = N_S^-(v) \cup \{v\} \quad \text{and} \quad N_S^+[v] = N_S^+(v) \cup \{v\}. $$

When $S = V(D)$, these notations simplify to

$$ N_D^-(v), \ N_D^+(v), \ N_D^-[v], \ N_D^+[v], \ \deg_D^-(v), \ \text{and} \ \deg_D^+(v). $$
The subscript *D* can be omitted when the digraph *D* is clear from context [21]. For a graph *G*, $\Delta = \Delta(G)$ and $\delta = \delta(G)$ denote the maximum and minimum degrees, respectively. Similarly, for a digraph *D*,

$$ \Delta^+ = \Delta^+(D), \quad \delta^+ = \delta^+(D), \quad \Delta^- = \Delta^-(D), \quad \text{and} \quad \delta^- = \delta^-(D) $$

denote the maximum and minimum out-degrees and in-degrees, respectively. For subsets $A, B \subseteq V(D)$, $(A, B)_D$ denotes the set of arcs from $A$ to $B$ in $D$, and for $S \subseteq V(D)$, $D\langle S \rangle$ represents the subdigraph induced by $S$ [21]. Thus, for each vertex $v$ in $D$, define

$$ N[v] = N^-[v] \cup N^+[v]. $$

Let *D* be a digraph of order *n* with minimum in-degree $\delta^- \ge 1$. Then the 2-total packing number satisfies

$$ L_2^t(D) \le \frac{2n}{\delta^- + 1}, $$

with equality if and only if $D \in \Omega$. For any digraph *D* of order *n* without isolated vertices and maximum out-degree $\Delta^+$, the 2-total domination number satisfies

$$ \gamma_2^t(D) \ge \frac{2n}{\Delta^+ + \frac{3}{2}}, $$

and equality holds if and only if $D \in \Theta$. For any directed tree *T* of order *n* $\ge 2$, it holds that

$$ \gamma_2^t(T) \le L_2^t(T). $$

For a directed tree [21] *T* of order *n* with *e* end-vertices and *p* penultimate vertices, the 2-total domination number satisfies

$$ \gamma_2^t(T) \ge \frac{2n + e - p + 2}{3}. $$

## 3.2 Problem Distance Graph

The substantial discrepancy between these bounds among $\chi(\mathbb{R}^n)$ of the $n$-dimensional Euclidean space $\mathbb{R}^n$ indicates a big open obstacle: decreasing or shrinking this range is a critical issue. For any two vertices $a$ and $b$ within a graph $G$, we denote the distance between them by $D(a, b)$. Define $\Gamma_i(a)$ as the induced subgraph formed by all vertices located at distance $i$ from vertex $a$. Notably, the subgraph $\Gamma_1(a)$ represents the neighborhood of $a$, which we denote by $[a]$. Additionally, the notation $a^\perp$ refers to the ball of radius one centered at the vertex $a$.

Thus, we presented question provided in [27] of whether a distance graph must adhere precisely to the aforementioned structure ($l \sim \frac{2-\sqrt{2}}{2}n, a \sim \sqrt{l}$) in order to achieve a chromatic number bounded below by $(1.207...+o(1))^n$. The problem may be formalized as follows. Let $\mathfrak{G}_1 = \mathfrak{G}_1(n; 0, 1; n-l, l)$ denote the family of all distance graphs $G = (V, E)$ such that $V \subseteq \Sigma$ (where each vertex, represented as a vector in $\mathbb{R}^n$, contains precisely $n-l$ zeros and $l$ ones), and $E$ for some (arbitrary) $a$. This construction thus affords two degrees of freedom within the class: an arbitrary choice of $V$ (albeit with the coordinate structure of its elements prescribed in advance) and an arbitrary $a$ subject to sensible constraints (e.g., $a$ cannot exceed the maximum pairwise distance in $\Sigma$). Define

$$ \chi_1 = \chi_1(n; 0, 1; n-l, l) = \max_{G \in \mathfrak{G}_1} \chi(G). \qquad (5) $$

Evidently, in this framework, $\chi_1(n; 0, 1; n-l, l) \ge (1.207... + o(1))^n$ holds whenever $l \sim \frac{2-\sqrt{2}}{2}n$, whereas no comparable lower bound is known for other values of $l$. We shall assume $l \asymp n$.

**Theorem 3.1 ([16]).** The digraph $H_n$ is a large minimal irregular oriented graph of order $n$ and size $\|H_n\| \sim \frac{n^2}{2}$.

**Theorem 3.2 ([16].)** The digraph $G_n$ is a small maximal irregular oriented graph of order $n$ and size $\|H_n\| = \Theta(\sqrt[3]{n})$. Moreover, if $m = t$ and $n = st + t$, then: $\|H_n\| \sim (4\sqrt{\frac{2}{3}}\sqrt[3]{n})$ wherein the asymptotic coefficient is the largest possible.
Although this constraint may appear restrictive at first, it is justified by the fact that when $l = o(n)$, the upper bounds on $\chi_1$ established in [35] are subexponential, precluding the possibility of achieving lower bounds of the form $(1.207...+o(1))^n$. It is well-known that $C_n^{l-t} = (v_0+o(1))^n$, where $v_0 = v_0(l, t) > 1$ is a constant. The following result holds:

**Theorem 3.3 ([27]).** Let $G = (V, E)$ be a graph and $t > 0$ be an integer where $G_t = (V_t, E_t) \in \mathfrak{G}_1$. The lower bound of $\chi(G)$ satisfy

$$ \chi_1 \geq \max_t \frac{(v_0(l,t) + o(1))^n}{C_n^{p(l,t)-1}}. \qquad (6) $$

*Proof.* Let all parameters from the statement of the theorem be fixed. Define a natural number $r$ by the condition

$$ (l - t + 1) \left( 2 + \frac{t-1}{r+1} \right) \leqslant n \leqslant (l - t + 1) \left( 2 + \frac{t-1}{r} \right), $$

and select the graph $G_t = (V_t, E_t) \in \mathfrak{G}_1$ as follows. First, let $V_t \subset \Sigma$ be defined by

$$ V_t = \bigcup_{u=t+r}^{t+2r} V_t^u, \qquad (7) $$

where $V_t^u = \{\mathbf{x} = (x_1, \dots, x_n) \in \Sigma : |\{i \leqslant t + 2r : x_i = 1\}| = u\}$. It is straightforward to verify that the scalar product of any two vectors from $V_t$ cannot be less than $t$. Moreover, standard combinatorial arguments combined with Stirling's formula demonstrate that $|V_t| = (v_0(l, t)+o(1))^n$. The results presented in [36] establish that if the pairwise scalar products of vectors in some $V \subset \Sigma$ satisfy the same lower bound condition $t$ as in $V_t$, then it follows that $|V| \leqslant |V_t|$, thereby confirming the optimality of the construction of $V_t$. Next, consider the edge set

$$ E_t = \{(\mathbf{x}, \mathbf{y}) \in V_t \times V_t : |\mathbf{x} - \mathbf{y}| = \sqrt{2p}\}. \qquad (8) $$

We apply the inequality

$$ \chi_1 \geq \chi(G_t) \geq \frac{|V_t|}{\alpha(G_t)}, \qquad (9) $$

where $\alpha(G_t)$ denotes the independence number of the graph. Hence, the desired result will follow if we establish that $\alpha(G_t) \leqslant C_n^{p-1}$. According to [33, 34], let $Q = \{\mathbf{x}_1, \dots, \mathbf{x}_s\} \subset V_t$ be an arbitrary set of vectors such that the distance between any two distinct vectors is not equal to $\sqrt{2p}$. Consequently, their scalar products differ from $l-p$, and conversely. Since $l-2p < t$ and $Q \subset V_t$, the latter condition can equivalently be expressed as "not congruent to $l$ modulo $p$."

To each vector $\mathbf{x}_i \in Q$, associate a polynomial $F_{\mathbf{x}_i} \in \mathbb{Z}/p\mathbb{Z}[y_1, \dots, y_n]$ defined by

$$ F_{\mathbf{x}_i}(\mathbf{y}) = \prod_{k \neq l} (\mathrm{mod} p)(k - \langle \mathbf{x}_i, \mathbf{y} \rangle), \qquad (10) $$

where $\langle \mathbf{x}, \mathbf{y} \rangle$ denotes the scalar product of vectors, and the product ranges over all residues $k$ modulo $p$ except those congruent to $l$ (mod $p$). Note that for $\mathbf{y} = (y_1, \dots, y_n) \in Q$, each coordinate $y_j \in \{0, 1\}$. Thus, powers $y_j^\beta$ can be replaced by $y_j$ without altering the polynomial's value. Applying this reduction to each variable in $F_{\mathbf{x}_i}$ yields a new polynomial $\tilde{F}_{\mathbf{x}_i}$, which, like its predecessor, satisfies the property

$$ \tilde{F}_{\mathbf{x}_i}(\mathbf{x}_j) \equiv 0 \pmod{p} \quad \text{if and only if} \quad \langle \mathbf{x}_i, \mathbf{x}_j \rangle \not\equiv l \pmod{p}. \qquad (11) $$

Therefore, from equations (7) through (11), the assertion (6) follows. $\square$

**Corollary 3.4.** If $l_0 \geq \frac{2-\sqrt{2}}{2}$, then $\max_t c_0(l, t) = 1.207\dots$, i.e.,

$$ \chi_1 \geq (1.207\dots + o(1))^n. $$
Corollary 3.4 answers our very first question: a distance graph need not have the structure considered by Frankl and Wilson for its chromatic number to be sufficiently large. Previously, for $l = 0.5n$ say, we had $\chi_1 \ge (1.139... + o(1))^n$; now we have $\chi_1 \ge (1.207... + o(1))^n$, and so on. Note that the problem we have analyzed admits a significant and very important generalization. Accordingly, numerous recent studies have dealt with graphs of this and even completely general type.

Let all quantities of interest be fixed $n, r, a_1, ..., a_r, l_1, ..., l_r, \chi_g$. Let be consider $\bar{s} = a_1^2 l_1 + ... + a_r^2 l_r$ and take an arbitrary integer $t \le \bar{s}$. Consider the vector $\mathfrak{m}_t = (m_1, ..., m_r)$ and the matrix

$$ \mathfrak{M}_t = \begin{pmatrix} m_{1,1} & m_{1,2} & \dots & m_{1,r} \\ m_{2,1} & m_{2,2} & \dots & m_{2,r} \\ \dots & \dots & \dots & \dots \\ m_{r,1} & m_{r,2} & \dots & m_{r,r} \end{pmatrix}, \qquad (12) $$

**Proposition 3.1.** Let $\mathfrak{M}_t$ be a matrix given by (12). Then,

1. $m_i$ and $m_{i,j}$ are nonnegative integers for all indices $i, j = 1, ..., r$;

2. For each $i \in \{1, ..., r\}$ the equality $\sum_{j=1}^r m_{i,j} = m_i$ holds;

3. For each $j \in \{1, ..., r\}$ the equality $\sum_{i=1}^r m_{i,j} = l_j$ holds;

4. $m_1 + \dots + m_r = \sum_{i,j=1}^r m_{i,j} = n$;

According to Proposition 3.1, consider $k_i = \min\langle \mathbf{x}, \mathbf{y} \rangle$, where the minimum is taken over all pairs of vectors from the set $\{\mathbf{x} = (x_1, ..., x_{m_i}) : x_\nu \in \{a_1, ..., a_r\}, |\{\nu : x_\nu = a_j\}| = m_{i,j}\}$ for $i = 1, ..., r$ (the correctness of the definition of $k_i$ follows from the already postulated properties (1)–(4)). Then $k_1 + \dots + k_r \ge t$. Next, let

$$ L(\mathfrak{m}_t, \mathfrak{M}_t) = \frac{m_1!}{m_{1,1}!m_{1,2}!\dots m_{1,r}!} \frac{m_2!}{m_{2,1}!m_{2,2}!\dots m_{2,r}!} \dots \frac{m_r!}{m_{r,1}!m_{r,2}!\dots m_{r,r}!} \qquad (13) $$

and let $L_t = \max_{\mathfrak{m}_t, \mathfrak{M}_t} L(\mathfrak{m}_t, \mathfrak{M}_t)$. Fix an integer $b \ge 2$ and define $p_{t,b}$ as the smallest prime number such that $\bar{s} - bp_{t,b} < t$. Denote by $D_{t,b}$ the quantity

$$ D_{t,b} = \sum_{i_1, \dots, i_{r-1} \in \mathcal{A}} C_n^{i_1} C_{n-i_1}^{i_2} \dots C_{n-i_{r-1}}^{i_{r-1}} \qquad (14) $$

where $\mathcal{A} = \{(i_1, ..., i_{r-1}) : \alpha, i_1 + 2i_2 + \dots + (r-1)i_{r-1} \le p_{t,b} - 1, \ i_1, ..., i_{r-1} \in \mathbb{N} \cup \{0\}\}$ and $\alpha$ is the term $i_1 + \dots + i_{r-1} \le n$.

**Theorem 3.5 ([27]).** Let $G = (V, E)$ be a graph and $t > 0$ be an integer where $G_t = (V_t, E_t) \in \mathfrak{G}_1$. According to Theorem 3.3, let $\mathfrak{M}_t$ be a matrix given by (12). Then,

$$ \chi_g \ge \max_t \max_b \sqrt[b-1]{\frac{L_t}{D_{t,b}}}. \qquad (15) $$

*Proof.* Let all parameters involved in the formulation of the theorem be fixed. Consider the set

$$ V = \{ \mathbf{x} = (x_1, \dots, x_n) : \begin{array}{l} x_i \in \{a_1, \dots, a_r\}, \quad |\{\nu = 1, \dots, m_1 : x_\nu = a_j\}| = m_{1,j} \\ |\{\nu = m_1 + 1, \dots, m_1 + m_2 : x_\nu = a_j\}| = m_{2,j}, \dots, \\ |\{\nu = m_1 + m_2 + \dots + m_{r-1} + 1, \dots, n : x_\nu = a_j\}| = m_{r,j} \end{array} \} $$

It is evident that $|V| = L(\mathfrak{m}_t, \mathfrak{M}_t)$, and from Proposition 3.1 of the “gothic parameters,” it follows that all scalar products within $V$ are bounded below by $t$. Moreover, it is not feasible to proceed identically to the proof of Theorem 3.3; namely, to impose the forbidden distance and subsequently estimate the independence number of the resulting graph from above. Although such a procedure is possible, it generally yields rather weak bounds. Among which one possesses a known chromatic number satisfying $\chi \ge \sqrt[b-1]{L_t/D_{t,b}}$. This completes the proof of the theorem. $\square$
## 3.3 Bounds for the spread of the line graph

The concept of a *graph's spread*, particularly when applied to the line graph, involves spectral graph properties. The *Laplacian spread* of a line graph is defined as the numerical difference between its greatest Laplacian eigenvalue and its second smallest Laplacian eigenvalue. This metric captures important spectral features that reflect the graph's underlying structural properties and can be utilized in analyzing the behavior and dynamics of complex networks. Some properties of an (*n*, *m*) graph had presented among Lemma 3.6.

**Lemma 3.6 ([1]).** Let $G$ be an $(n, m)$ graph. Then

1. If $m = n$, then $S_{\mathcal{L}}(G) = q_1 - q_n = S_{\mathcal{Q}}(G)$.

2. If $m > n$, then $S_{\mathcal{L}}(G) = q_1 \geq S_{\mathcal{Q}}(G)$, with equality if and only if $G$ has a bipartite component.

3. If $m < n$, then $S_{\mathcal{L}}(G) = q_1 - q_m \leq q_1 = S_{\mathcal{Q}}(G)$, with equality, for example, for $G = C_n \cup K_2$, when $n$ is even.

Let us considered $G$ be an arbitrary graph. it was established that $\text{irr}_s(G) \leq q_1$, with equality if and only if $G$ is a bipartite regular graph. If $G$ is a unicyclic connected graph with even cycle, from Lemma 3.6, we find that $S_{\mathcal{L}}(G) = S_{\mathcal{Q}}(G) = q_1$. Thus $\text{irr}_s(G) \leq S_{\mathcal{L}}(G) = S_{\mathcal{Q}}(G)$. Let $T$ be a tree. The second smallest Laplacian eigenvalue of $T$ is referred as the algebraic connectivity of $T$, it is denoted by $a(T)$. Then $a(T) \leq 0.49$. Moreover, an upper bound for the algebraic connectivity of a tree in function of $\text{diam}(T)$,

$$a(T) \leq 1 - \cos \frac{\pi}{\text{diam}(T) + 1} \qquad (16)$$

**Theorem 3.7 ([1]).** Let $e$ be an edge of the graph $G$. Let $q_1, \dots, q_n$ and $s_1, \dots, s_n$ be the signless Laplacian eigenvalues of $G$ and of $G - e$, respectively. Then $0 \leq s_n \leq q_n \leq s_{n-1} \leq \dots \leq s_2 \leq q_2 \leq s_1 \leq q_1$.

The lemma 3.8 attributed to [5] claims for a complete graph $G \cong K_n$ (where $|V(G)| = n$), and letting $\bar{G}$ be its complement (notated as $G$ in the statement, likely a typographical error), the inequality $H(\bar{G}) < H(\bar{G} + e)$ holds for every edge $e \in E(G)$.

**Lemma 3.8 ([5]).** Let $G$ be a simple graph with $|V(G)| = n$ with $G \cong K_n$. Then for every edge $e \in E(G)$, where $G$ is the complement of $G$, $H(G) < H(G + e)$.

For a bipartite graph $G$ with $n$ vertices and matching number $\nu(G) = k$ provided in Theorem 3.9, the graph $K_{k,k-n}$ uniquely maximizes $H(G)$. Here, the bipartite environment (emphasized as $G$ bipartite with $|V(G)| = n$) restricts analysis to balanced or unbalanced complete bipartitions, with the matching number environment $\nu(G) = k$ bounding perfect matchings.

**Theorem 3.9 ([5]).** Let $G$ represents a bipartite graph with $n$ vertices and matching number $k$. Then $K_{k,k-n}$ is the unique graph with the maximum Harary index.

## 3.4 Note On the total irregularity

In this section, suppose $r = (r_1, r_2, \dots, r_n)$ and $s = (s_1, s_2, \dots, s_n)$ are two non-increasing vectors in $\mathbb{R}^n$. If $\sum_{i=1}^k r_i \leq \sum_{i=1}^k s_i$, $1 \leq k \leq n-1$, and $\sum_{i=1}^n r_i = \sum_{i=1}^n s_i$, then we say that $r$ majorizes $s$, and we write $r \leq s$. There are several graph parameters for measuring irregularity of graphs [8]. One of such parameters that related to degree sequence of the graph under consideration was introduced by Albertson. Define the imbalance of an edge $xy$ as $|d(x) - d(y)|$, and the sum of all edge imbalances in a graph is called its irregularity. Albertson [4] determined the maximum irregularity of some classes of graphs and proved that the irregularity of an arbitrary $n$-vertex graph is $\leq \frac{4}{27}n^3$.

Dimitrov and Škrekovski [12] compared the irregularity and the total irregularity of graphs. When $G$ is an $n$-vertex connected graph, they proved that $ir_t(G) \leq \frac{n^2}{4} \text{irr}(G)$. It is also shown
that, if $G$ is a tree, then $\text{irr}_t(G) \le (n-2)\text{irr}(G)$. Denote by $\mathcal{T}$ the set of all trees of order greater than two. Let $\mathcal{P} = (P_\in, P_\Delta, P_\Delta, \dots)$. It is an elementary task [15] to verify that if $T \in \mathcal{P}$, then $\text{irr}(T) = 2$.

**Lemma 3.10 ([15]).** Among trees of order $n$, the star $S_n$ is the unique tree with greatest irregularity, satisfying:

$$ \text{irr}(s_n) = (n-1)(n-2) $$

Let $G$ and $H$ be two connected graphs with a same cyclomatic number [8] containing degree sequences $x = (x_1, x_2, \dots, x_n)$ and $y = (y_1, y_2, \dots, y_n)$, respectively. If $x \le y$ then $\text{irr}_t(G) \le \text{irr}_t(H)$. The equality holds if and only if $x = y$. If $G$ is a connected graph with $n$ vertices and cyclomatic number $c$, then:

$$ n_1(G) = 2 - 2c + \sum_{i=3}^{\Delta(G)} (i-2)n_i \quad \text{and} \quad n_2(G) = 2c + n - 2 - \sum_{i=3}^{\Delta(G)} (i-1)n_i $$

Let $\text{Gr}^1[n, c, p]$ be the set of all connected graphs on $n$ vertices with cyclomatic number $c$ and pendant vertex number $p$.

**Theorem 3.11 ([8]).** Let $G$ be a graph in set $\text{Gr}^1[n, c, p]$. Then:

$$ \frac{1}{2}(2c - 2 + n)(n + 2 - 2c) - 2 \left( p - \frac{1}{2}n + c - 1 \right)^2 \le \text{irr}_t(G) \le p(2n - p - 1) + 2(n - 1)(c - 1). $$

equality in left holds if and only if:

$$ D(G) = \left( \overbrace{3, \dots, 3}^{p+2(c-1)}, \overbrace{2, \dots, 2}^{n-2(p+c-1)}, \overbrace{1, \dots, 1}^{p} \right), \quad D(G) = \left( p + 2c, \overbrace{2, \dots, 2}^{n-p-1}, \overbrace{1, \dots, 1}^{p} \right). $$

**Theorem 3.12 ([15]).** Let $T_1, T_2, T_3, T_4, T_5, T_7, T_8$, and $T_{17}$ be the trees. Then:

1. $\text{irr}(T) = 6$ if and only if $T \in \Gamma(T_1)$,

2. $\text{irr}(T) = 8$ if and only if $T \in \Gamma(T_2)$,

3. $\text{irr}(T) = 10$ if and only if $T \in \Gamma(T_3) \cup \Gamma(T_4)$,

4. $\text{irr}(T) = 12$ if and only if $T \in \Gamma(T_5) \cup \Gamma(T_7) \cup \Gamma(T_8) \cup \Gamma(T_{17})$,

**Theorem 3.13 ([8]).** Let $n, c, p$ and $q$ be four positive integers such that : $q \ge p, n > \frac{1}{2}q^2 + (2c - \frac{3}{2})q + (c-1)(2c-3)$. if $c \ge 2$ or $(c = 1, q \ge 3)$ or $(c = 0, q \ge 5)$ then for $G \in \text{Gr}^1[n, c, p]$ and $H \in \text{Gr}^1[n, c, p]$ we have $\text{irr}_t(G) < \text{irr}_t(H)$.

**Theorem 3.14 ([8]).** Let $n, k$ and $c$ be three positive integers such that $n > 2c^2 - 3c + 2$ and $1 \le k \le c$. Then the among all connected chemical graphs with cyclomatic number $c$ ($\le$) the graphs with degree sequence:

$$ \left( \overbrace{4, \dots, 4}^{k-1}, \overbrace{3, \dots, 3}^{2(c+k-2)}, \overbrace{2, \dots, 2}^{n-(3k+2c-5)} \right) $$

have the $k^{th}$ minimal value with respect to the total irregularity.

The transitive tournament $T_n$ is the unique largest irregular [16] oriented $n$-graph.

$$ \|T_n\| = \frac{1}{2}n(n-1) \sim \frac{1}{2}n^2. $$

An $n$-set of $n$ degree pairs is called minimum and symmetric if the set is symmetric and with smallest possible sum of semi-degrees. Since $U_s$ is among the smallest irregular digraphs [16], the complement
$\overline{U}_s$ (in the complete symmetric digraph $K_s^*$) is one of the largest digraphs among irregular digraphs of order $s$. One can see the following consequence of $t = \frac{1}{2}(\sqrt{8s+1}-1) \sim \sqrt{2s}$ which implies the equality $t^2 = 2s-t$. Therefore, the asymptotic values of the sizes of $U_s, \overline{U}_s$ are as follows:

$$ \|\overline{U}_s\| = \frac{1}{2} \sum_{i=1}^{t} i(i-1) = \frac{1}{6}t(t^2-1) = \frac{1}{6}(t^3-t) \sim \frac{\sqrt{2}}{3}\sqrt[3]{s} $$

and $\frac{1}{6}t(2s-t-1) = \frac{1}{3}ts + O(t^2)$. Then, $\|\overline{U}_s\| = \|\overline{K}_s^*\| - \|U_s\| = s(s-1) - \|U_s\| \sim s^2$.

## 3.5 Conclusion

This work surveys and unifies recent advances across several interrelated areas of graph theory, including fuzzy graphs, domination parameters in directed and undirected graphs, chromatic properties of distance graphs in $\mathbb{R}^n$, spectral spreads of line graphs, and various measures of graph irregularity. We have presented sharp bounds for k-domination, 2-total domination, and 2-total packing numbers in digraphs and directed trees, with precise characterisations of the extremal families $\Omega$ and $\Theta$. Structural properties of special tree families $\mathcal{F}_0$ and $\mathcal{T}$ were exploited to derive tight relations between domination, total domination, and related invariants.

In the domain of distance graphs, we revisited the Raigorodskii–Frankl–Wilson-type constructions and their generalisations (Theorems 3.3 and 3.5, Corollary 3.4), showing that chromatic numbers at least $(1.207... + o(1))^n$ are attainable even beyond the classical parameter regime $l \sim \frac{2-\sqrt{2}}{2}n$. These results confirm that the specific coordinate structure assumed in earlier breakthrough lower bounds is not essential for achieving near-optimal exponential growth of $\chi(\mathbb{R}^n)$. Spectral aspects were addressed through bounds on Laplacian and signless Laplacian spreads of line graphs (Lemma 3.6 and Theorem 3.7), while extremal Harary indices in bipartite and matching-constrained settings were recalled (Theorem 3.9).

The study of graph irregularity was significantly enriched by sharp upper and lower bounds on the total irregularity $\text{irr}_t(G)$ for connected graphs with given cyclomatic number $c$ and number of pendant vertices $p$ (including explicit degree sequences attaining equality), as well as by majorisation principles linking degree sequences to $\text{irr}_t$. The asymptotic size of maximal and minimal irregular oriented graphs was also clarified. Collectively, these results contribute to a deeper understanding of domination, colouring, spectral, and irregularity phenomena across undirected graphs, digraphs, fuzzy graphs, and geometric realisations, while highlighting numerous directions for future investigation, particularly the further narrowing of gaps in high-dimensional chromatic numbers and the complete classification of extremal configurations for the total irregularity index.

## References

[1] E. Andrade, E. Lenes, E. M. Zepeda, M. Robbiano, R. Z. Jonnathan, *Bounds for different spreads of line and total graphs*, Journal of Linear Algebra and its Applications. 579(1) (2023), Pages 365-381, DOI:10.1016/j.laa.2019.06.007.

[2] N. D. Roussopoulos, *A max {$m,n$} algorithm for determining the graph H from its line graph G*. Information Processing Letters. 2(4) (1973), 108-112.

[3] M. Klazar, *A general upper bound in extremal theory of sequences*, Commentationes Mathematicae Universitatis Carolinae, **33**(4) (1992), 737-746.

[4] M. O. Albertson, *The irregularity of a graph*, Ars Combinatoria. 46 (1997), 219-225.

[5] H. Deng, S. Balachandran, S. Elumalaid, T. Mansourd, *Harary index of bipartite graphs*, Electronic Journal of Graph Theory and Applications. 7 (2019), Pages 365-372, DOI:10.5614/ejgta.2019.7.2.12.
[6] A. M. Raigorodskii, D. D. Cherkashin, *Extremal problems in hypergraph colourings*, Russian Mathematical Surveys. 75(1) (2020), Pages 89–146, DOI:10.1070/RM9905.

[7] M. K. Baca, KM. Muthugurupackiam, S. R. Kathiresan, *Modular irregularity strength of graphs*, Electronic Journal of Graph Theory and Applications. 8(2) (2020), Pages 435–443, DOI:10.5614/ejgta.2020.8.2.19.

[8] A. Ghalavand, A. R. Ashrafi, *Ordering of c-cyclic graphs with respect to total irregularity*, Journal of Applied Mathematics and Computing. 63 (2020), Pages 707–715, DOI:10.1007/s12190-020-01335-6.

[9] E. B. Lenes, A. M. Marrero, E. M. Zepeda, *Total irregularity of graphs under Cartesian product*, Discussiones Mathematicae Graph Theory. 41(2) (2021), 567–584, DOI:10.7151/dmgt.2351.

[10] M. Robbiano, B. Sanhueza, *On the total irregularity of graphs with fixed minimum degree*, Applied Mathematics and Computation. 415 (2022), 126712, DOI:10.1016/j.amc.2021.126712.

[11] I. Gutman, *The energy of a graph: old and new results*, in Algebraic Combinatorics and Applications: Proceedings of the Euroconference, Algebraic Combinatorics and Applications (ALCOMA). (2001), held in Germany, September 12–19, 1999 (pp. 196-211). Berlin, Heidelberg: Springer Berlin Heidelberg.

[12] D. Dimitrov, R. Škrekovski, *Comparing the irregularity and the total irregularity of graphs*, Ars Math. Contemp. 9(1) (2015), 45–50, DOI:10.26493/1855-3974.341.bab.

[13] M. Ridwan, H. Assiyatun, E. T. Baskoro, *The dominating partition dimension and locatingchromatic number of graphs*, Electronic Journal of Graph Theory and Applications. 11(2) (2023), 455–465, DOI:10.5614/ejgta.2023.11.2.10.

[14] O. Favaron, H. Karam, S. M. Sheikholeslam, Bounding the total domination subdivision number of a graph in terms of its order, Jouenal combinatorics optimal. 21 (2011), 209–218, DOI:10.1007/s10878-009-9224-y.

[15] G. H. F. Tabar, I. Gutman, R. Nasiri, Extremely irregular trees, Bulletin (Académie Serbe Des Sciences et Des Arts. Classe Des Sciences Mathématiques et Naturelles. Sciences Mathématiques). 38 (2013).

[16] J. Gorska, z. l. Skupie, F. Krakow, Z. Dziechcinska, H. Z. Majcher, J. Michael, Extremal Irregular Digraphs, journal of graph theory. 38 (2015), 791–800, DOI:10.7151/dmgt.2031.

[17] M. Abdul, N. Rao, S. M. Shaw, Inverse Domination in Fuzzy Planar Graphs, International Journal of Pure and Applied Mathematics. 120(6) (2018), 4293–4303

[18] Ramy S Shaheen, K-domination number of products of two directed cycles and two directed paths, International Journal of Computing Science and Mathematics. 9(2) (2018), 197–206, DOI:10.1504/IJCSM.2018.091734.

[19] J. Raczek, on Domination Multisubdivision Number of Unicyclic Graphs, Opuscula Math. 38(3) (2018), 406–425, DOI:10.7494/OpMath.2018.38.3.409.

[20] M. Borowiecki, A. Fiedorowicz, E. Sidorowicz, Z. Tuza, Independent (k+1)-domination in k-trees, Discrete Applied Mathematics. 284 (2020), 99–110, DOI:10.1016/j.dam.2020.03.019.

[21] M. D. Ali, S. Babak, Total 2-Domination Number in Digraphs and Its Dual Parameter, Discussiones Mathematicae: Graph Theory. 43(3) (2023), DOI:10.7151/dmgt.2387.

[22] J. Hamoud, D. Abdullah, Topological Indices with Degree Sequence $\mathcal{D}$ of Tree, Lobachevskii Journal of Mathematics. 46(8) (2025), 4249–4264, DOI:10.1134/S1995080225606769.
[23] J. Hamoud, D. Abdullah, Albertson index and Sigma index in trees given by degree sequences, Chebyshevskii sbornik. 26(3) (2025), DOI:10.22405/2226-8383-2025-26-3-2-11.

[24] A. M. Raigorodsky, *Chromatic numbers of distance graphs*, Chebyshevsky Collection.6(3) (2005), p.159-170.

[25] N. Nakagawa, *On strongly regular graphs with parameters (k,0,2) and their antipodal double cover*, Hokkaido Math. Soc. 30(2001), pp. 431–450.

[26] V. V. Nosov, *On Automorphisms of Strongly Regular Graph with The Parameters (1276,50,0,2)*, Chebyshevskii Sbornik. 17(3) (2016), pp:178-185, DOI:10.22405/2226-8383-2016-17-3-178-185

[27] A. M. Raigorodsky, *On the structure of distance graphs having a large chromatic number*, Chebyshevsky Collection, 6(3) (2005), pp.151-158.

[28] A. Soifer, *Mathematical coloring book*, Center for Excellence in Mathematical Education. (1997).

[29] H. Hadwiger, *Ungelöste Probleme N 40*, Elemente der Math. 16 (1961), P.103-104.

[30] H. Hadwiger, *Ein Überdeckungssatz für den Euklidischen Raum*, Portugaliae Math. 4 (1944), P.140-144.

[31] N. G. de Bruijn and P. Erdös, *A colour problem for infinite graphs and a problem in the theory of relations*, Proc. Koninkl. Nederl. Acad. Wet., Ser. A. 54(5) (1951), P.371-373.

[32] D. G. Larman and C. A. Rogers, *The realization of distances within sets in Euclidean space*, Mathematika. 19 (1972), P.1-24.

[33] P. Frankl, R. M. Wilson, *Intersection theorems with geometric consequences*, Combinatorica. 1 (1981), P.357-368.

[34] A. M. Raigorodsky, *On the chromatic number of space*, UMN. 55(2) (2000), pp. 147-148.

[35] A. M. Raigorodsky, *Borsuk's problem for integer polyhedra*, Mat. collection. 193(10) (2002), pp. 139-160.

[36] R. Ahlswede, L.H. Khachatrian, *The complete intersection theorem for systems of finite sets*, Europ. J. Combin. 18 (1997), P.125-136.