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.

We will discuss the vertex-distinguishing I-total colorings and vertex-distinguishing VI-total colorings of three types of graphs: \( S_m \lor F_n, S_m \lor W_n \) and \( F_n \lor W_n \) in this paper. The optimal vertex-distinguishing I (resp. VI)-total colorings of these join graphs are given by the method of constructing colorings according to their structural properties and the vertex-distinguishing I (resp. VI)-total chromatic numbers of them are determined.

A graph is called set-reconstructible if it is determined uniquely (up to isomorphism) by the set of its vertex-deleted subgraphs. The maximal subgraph of a graph \( H \) that is a tree rooted at a vertex \( u \) of \( H \) is the limb at \( u \). It is shown that two families \( \mathcal{F}_1 \) and \( \mathcal{F}_2 \) of nearly acyclic graphs are set-reconstructible. The family \( \mathcal{F}_1 \) consists of all connected cyclic graphs \( G \) with no end vertex such that there is a vertex lying on all the cycles in \( G \) and there is a cycle passing through at least one vertex of every cycle in \( G \). The family \( \mathcal{F}_2 \) consists of all connected cyclic graphs \( H \) with end vertices such that there are exactly two vertices lying on all the cycles in \( H \) and there is a cycle with no limbs at its vertices.

In this paper, we determine the second largest number of maximal independent sets and characterize those extremal graphs achieving these values among all twinkle graphs.

In this paper, we characterize the set of spanning trees of \( G^1_{n,r} \) (a simple connected graph consisting of \( n \) edges, containing exactly one 1-edge-connected chain of \( r \) cycles \( C^1_r \) and \( G^1_{n,r} \setminus C^1_r \) is a forest). We compute the Hilbert series of the face ring \( k[\Delta_s(G^1_{n,r})] \) for the spanning simplicial complex \( \Delta_s(G^1_{n,r}) \). Also, we characterize associated primes of the facet ideal \( I_F(\Delta_s(G^1_{n,r})) \). Furthermore, we prove that the face ring \( k[\Delta_s(G^1_{n,r})] \) is Cohen-Macaulay.