The paired domination subdivision number \( sd_p(G) \) of a graph \( G \) is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the paired domination number of \( G \). We prove that the decision problem of the paired domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the paired domination multisubdivision number of a nonempty graph \( G \), denoted by \( msd_p(G) \), as the minimum positive integer \( k \) such that there exists an edge which must be subdivided \( k \) times to increase the paired domination number of \( G \). We show that \( msd_p(G) \leq 4 \) for any graph \( G \) with at least one edge. We also determine paired domination multisubdivision numbers for some classes of graphs. Moreover, we give a constructive characterizations of all trees with paired domination multisubdivision number equal to 4.

Given a permutation \( \pi = (\pi_1, \pi_2, \pi_3, \ldots, \pi_n) \) over the alphabet \(\Sigma = \{0, 1, \ldots, n-1\}\), \(\pi_i\) and \(\pi_{i+1}\) are said to form an adjacency if \(\pi_{i+1} = \pi_i + 1\) where \(1 \leq i \leq n-1\). The set of permutations over \(\Sigma\) is a symmetric group denoted by \(S_n\). \(S_n(k)\) denotes the subset of permutations with exactly \(k\) adjacencies. We study four adjacency types and efficiently compute the cardinalities of \(S_n(k)\). That is, we compute for all \(k\) \(|S_n(k)|\) for each type of adjacency in \(O(n^2)\) time. We define reduction and show that \(S_n(n-k)\) is a multiset consisting exclusively of \(\mu \in \mathbb{Z}^+\) copies of \(S_n(0)\) where \(\mu\) depends on \(n\), \(k\) and the type of adjacency. We derive an expression for \(\mu\) for all types of adjacency.

The edge-distinguishing chromatic number \(\lambda(G)\) of a simple graph \(G\) is the minimum number of colors \(k\) assigned to the vertices in \(V(G)\) such that each edge \(\{u_i, u_j\}\) corresponds to a different set \(\{c(u_i), c(u_j)\}\). Al-Wahabi et al.\ derived an exact formula for the edge-distinguishing chromatic number of a path and of a cycle. We derive an exact formula for the edge-distinguishing chromatic number of a spider graph with three legs and of a spider graph with \(\Delta\) legs whose lengths are between 2 and \(\frac{\Delta+3}{2}\).

Motivated by the existing 3-equitable labeling of graphs, in this paper we introduce a new graph labeling called 3-equitable total labeling and we investigate the 3-equitable total labeling of several families of graphs such as \(C_n\), \(W_n\), \(SL_n\), \(S(K_{4,n})\) and \(K_n^{(4)}\).

The cluster deletion (CD) problem consists of transforming an input graph into a disjoint union of cliques by removing as few edges as possible. For general graphs, this is a combinatorial optimization problem that belongs to the NP-hard computational complexity class. In the present paper, we identify a new polynomially solvable CD subproblem. Specifically, we propose a two-phase polynomial algorithm that solves CD on (butterfly, diamond)-free graphs.

The maximum rectilinear crossing number of a graph \( G \) is the maximum number of crossings in a good straight-line drawing of \( G \) in the plane. In a good drawing, any two edges intersect in at most one point (counting endpoints), no three edges have an interior point in common, and edges do not contain vertices in their interior. A spider is a subdivision of \( K_{1,k} \). We provide both upper and lower bounds for the maximum rectilinear crossing number of spiders. While there are not many results on the maximum rectilinear crossing numbers of infinite families of graphs, our methods can be used to find the exact maximum rectilinear crossing number of \( K_{1,k} \) where each edge is subdivided exactly once. This is a first step towards calculating the maximum rectilinear crossing number of arbitrary trees.

For every connected graph \( F \) with \( n \) vertices and every graph \( G \) with chromatic surplus \( s(G) (n-1)(\chi(G)-1) + s(G), \) where \( \chi(G) \) denotes the chromatic number of \( G \). If this lower bound is attained, then \( F \) is called \( G \)-good. For all connected graphs \( G \) with at most six vertices and \( \chi(G) > 4 \), every tree \( T_n \) of order \( n > 5 \) is \( G \)-good. In the case of \( \chi(G) = 3 \) and \( G \neq K_6 – 3K_2 \), every non-star tree \( T_n \) is \( G \)-good except for some small \( n \), whereas \( r(S_n, G) \) for the star \( S_n = K_{1,n-1} \) in a few cases differs by at most 2 from the lower bound. In this note we prove that the values of \( r(S_n, K_6 – 3K_2) \) are considerably larger for sufficiently large \( n \). Furthermore, exact values of \( r(S_n, K_6 – 3K_2) \) are obtained for small \( n \).

Let \( \Gamma \) denote a bipartite and antipodal distance-regular graph with vertex set \( X \), diameter \( D \) and valency \( k \). Firstly, we determine such graphs \( \Gamma \) when \( D \geq 8 \), \( k \geq 3 \) and their corresponding quotient graphs are \( Q \)-polynomial: \( \Gamma \) is a \( 2d \)-cube if \( D = 2d \); \( \Gamma \) is either a \( (2d+1) \)-cube or the doubled Odd graph if \( D = 2d+1 \). Secondly, by defining a partial order \( \leq \) on \( X \) we obtain a grading poset \( (X, \leq) \) with rank \( D \). In [Š. Miklavič, P. Terwilliger, Bipartite \( Q \)-polynomial distance-regular graphs and uniform posets, J. Algebr. Combin. 225-242 (2013)], the authors determined precisely whether the poset \( (X, \leq) \) for \( D \)-cube is uniform. In this paper, we prove that the poset \( (X, \leq) \) for the doubled Odd graph is not uniform.

A double Italian dominating function on a digraph \( D \) with vertex set \( V(D) \) is defined as a function \( f: V(D) \to \{0,1,2,3\} \) such that each vertex \( u \in V(D) \) with \( f(u) \in \{0,1\} \) has the property that \(\sum_{x \in N^{-}[u]} f(x) \geq 3,\) where \( N^{-}[u] \) is the closed in-neighborhood of \( u \). The weight of a double Italian dominating function is the sum \(\sum_{v \in V(D)} f(v),\) and the minimum weight of a double Italian dominating function \( f \) is the double Italian domination number, denoted by \( \gamma_{dI}(D) \). We initiate the study of the double Italian domination number for digraphs, and we present different sharp bounds on \( \gamma_{dI}(D) \). In addition, several relations between the double Italian domination number and other domination parameters such as double Roman domination number, Italian domination number, and domination number are established.

A connected graph \( G = (V, E) \) is called a quasi-tree graph if there exists a vertex \( v_0 \in V(G) \) such that \( G – v_0 \) is a tree. In this paper, we determine the largest algebraic connectivity together with the corresponding extremal graphs among all quasi-tree graphs of order \( n \) with a given matching number.