We discuss the connections tying Laplacian matrices to abstract duality and planarity of graphs.

A set \( S \subseteq V(G) \) of a connected graph \( G \) is a co-secure dominating set, if \( S \) is a dominating set and for each \( u \in S \), there exists a vertex \( v \in V(G) \setminus S \), such that \( v \in N(u) \) and \( (S \setminus \{u\}) \cup \{v\} \) is a dominating set of \( G \). The minimum cardinality of the co-secure dominating set in a graph \( G \) is the co-secure domination number, \( \gamma_{cs}(G) \). In this paper, we characterise the Mycielski graphs with co-secure domination 2 and 3. We also obtained a sharp upper bound for \( \gamma_{cs}(G) \).

Given an n-connected binary matroid, we obtain a necessary and sufficient condition for its single-element coextensions to be \(n\)-connected.

In this paper, we provide bounds for the crossing number of mesh connected trees and 3-regular mesh of trees.

The ordinary factorial may be written in terms of the Stirling numbers of the second kind as shown by Quaintance and Gould and the odd double factorial in terms of the Stirling numbers of the first kind as shown by Callan. During the preparation of an expository paper on Wolstenholme’s Theorem, we discovered an expression for the odd double factorial using the Stirling numbers of the second kind. This appears to be the first such identity involving both positive and negative integers and the result is outlined here.

Let \( G \) be a \( k \)-connected (\( k > 2 \)) graph of order \( n \). If \( \chi(G) > n-k \), then \( G \) is Hamiltonian or \( K_k \vee (K_{n-2k}) \) with \( n > 2k+1 \), where \( \chi(G) \) is the chromatic number of the graph \( G \).

An \((n, r)\)-arc in \(PG(2, q)\) is a set of \(n\) points such that each line contains at most \(r\) of the selected points. We show that in the case of the existence of a \((101, 10)\)-arc in \(PG(2, 11)\) it only admits the trivial linear automorphism.

In this paper, we generalise the notion of distance irregular labeling introduced by Slamin to vertex irregular \(d\)-distance vertex labeling, for any distance \(d\) up to the diameter. We also define the inclusive vertex irregular \(d\)-distance vertex labeling. We give the lower bound of the inclusive vertex irregular \(1\)-distance vertex labeling for general graphs and a better lower bound on caterpillars. The inclusive labelings for paths \(P_n, n \equiv 0 \mod 3\), stars \(S_n\), double stars \(S(m,n)\), cycles \(C_n\), and wheels \(W_n\) are provided. From the inclusive vertex irregular \(1\)-distance vertex labeling on cycles, we derive the vertex irregular \(1\)-distance vertex labeling on prisms.

A Hamiltonian walk in a nontrivial connected graph \( G \) is a closed walk of minimum length that contains every vertex of \( G \). The 3-path graph \( P_3(G) \) of a connected graph \( G \) of order 3 or more has the set of all 3-paths (paths of order 3) of \( G \) as its vertex set and two vertices of \( P_3(G) \) are adjacent if they have a 2-path in common. With the aid of Hamiltonian walks in spanning trees of the 3-path graph of a graph, it is shown that if \( G \) is a connected graph with minimum degree at least 4, then \( P_3(G) \) is Hamiltonian-connected.

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 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.

Let \( G \) be a simple and finite graph. A graph is said to be decomposed into subgraphs \( H_1 \) and \( H_2 \) which is denoted by \(G = H_1 \oplus H_2,\) if \( G \) is the edge-disjoint union of \( H_1 \) and \( H_2 \). If \(G = H_1 \oplus H_2 \oplus \dots \oplus H_k,
\)where \( H_1, H_2, \dots, H_k \) are all isomorphic to \( H \), then \( G \) is said to be \( H \)-decomposable. Furthermore, if \( H \) is a cycle of length \( m \), then we say that \( G \) is \( C_m \)-decomposable and this can be written as \( C_m \mid G \). Where \( G \times H \) denotes the tensor product of graphs \( G \) and \( H \), in this paper, we prove that the necessary conditions for the existence of \( C_6 \)-decomposition of \( K_m \times K_n \) are sufficient. Using these conditions, it can be shown that every even regular complete multipartite graph \( G \) is \( C_6 \)-decomposable if the number of edges of \( G \) is divisible by 6.

Constructions of the smallest known trivalent graph for girths 17, 18, and 20 are given. All three graphs are voltage graphs. Their orders are 2176, 2560, and 5376, respectively, improving the previous values of 2408, 2640, and 6048.