The line graph \(L(G)\) of a connected graph G, has vertex set identical with the set of edges of \(G\), and two vertices of \(L(G)\) are adjacent if and only if the corresponding edges are adjacent in \(G\). Ivan Gutman et al examined the dependency of certain physio-chemical properties of alkanes in boiling point, molar volume, and molar refraction, heat of vapourization, critical temperature, critical pressure and surface tension on the Bertz indices of \(L'(G)\) Dobrynin and Melnikov conjectured that there exists no nontrivial tree \(T\) and \(i≥3\), such that \(W(L'(T)) = W(T)\). In this paper we study Wiener and Zagreb indices for line graphs of Complete graph, Complete bipartite graph and wheel graph.

A set S of vertices in a graph G is called a dominating set of G if every vertex in V(G)\S is adjacent to some vertex in S. A set S is said to be a power dominating set of G if every vertex in the system is monitored by the set S following a set of rules for power system monitoring. The power domination number of G is the minimum cardinality of a power dominating set of G. In this paper, we solve the power domination number for certain nanotori such as H-Naphtelanic, \(C_5C_6C_7[m,n]\) nanotori and \(C_4C_6C_8[m,n]\) nanotori.

Let \(G_k, (k ≥ 0)\) be the family of graphs that have exactly k cycles. For \(0 ≤ k ≤ 3\), we compute the Hadwiger number for graphs in \(G_k\) and further deduce that the Hadwiger Conjecture is true for such families of graphs.

Split domination number of a graph is the cardinality of a minimum dominating set whose removal disconnects the graph. In this paper, we define a special family of Halin graphs and determine the split domination number of those graphs. We show that the construction yield non-isomorphic families of Halin graphs but with same split domination numbers.

A graph \(G(v,E)\) with \(n\) vertices is said to have modular multiplicative divisor bijection \(f: V(G)→{1,2,.., n}\) and the induced function \(f*: E(G) → {0,1,2,…, n – 1}\) where \(f*(uv)=f(u)f(v)(mod\,\,n)\) for all \(uv \in E(G)\) such that \(n\) divides the sum of all edge labels of \(G\). This paper studies MMD labeling of an even arbitrary supersubdivision (EASS) of corona related graphs.

In this paper, the distance and degree based topological indices for double silicate chain graph are obtained.

In this paper, we introduce a new form of fuzzy number named as Icosikaitetragonal fuzzy number with its membership function. It includes some basic arithmetic operations like addition, subtraction, multiplication and scalar multiplication by means of \(\alpha\)-cut with numerical illustrations.

In this paper, we determine the wirelength of embedding complete bipartite graphs \(K_{2^{n-1}, 2^{n-1}}\) into 1-rooted sibling tree \(ST_n^1\), and Cartesian product of 1-rooted sibling trees and paths.

A dominator coloring is a proper vertex coloring of a graph \(G\) such that each vertex is adjacent to all the vertices of at least one color class or either alone in its color class. The minimum cardinality among all dominator coloring of \(G\) is a dominator chromatic number of \(G\), denoted by \(X_d(G)\). On removal of a vertex the dominator chromatic number may increase or decrease or remain unaltered. In this paper, we have characterized nontrivial trees for which dominator chromatic number is stable.

If every induced sub graph \(H\) of a graph \(G\) contains a minimal dominating set that intersects every maximal cliques of \(H\), then \(G\) is SSP (super strongly perfect). This paper presents a cyclic structure of some circulant graphs and later investigates their SSP properties, while also giving attention to find the SSP parameters like colourability, cardinality of minimal dominating set and number of maximal cliques of circulant graphs.

A set \(S\) of vertices in a graph \(G\) is said to be a dominating set if every vertex in \(V(G)\S\) is adjacent to some vertex in \(S\). A dominating set \(S\) is called a total dominating set if each vertex of \(V(G)\) is adjacent to some vertex in \(S\). Molecules arranging themselves into predictable patterns on silicon chips could lead to microprocessors with much smaller circuit elements. Mathematically, assembling in predictable patterns is equivalent to packing in graphs. In this pa-per, we determine the total domination number for certain nanotori using packing as a tool.

Among the varius coloring of graphs, the concept of equitable total coloring of graph \(G\) is the coloring of all its vertices and edges in which the number of elements in any two color classes differ by atmost one. The minimum number of colors required is called its equitable total chromatic number. In this paper, we obtained an equitable total chromatic number of middle graph of path, middle graph of cycle, total graph of path and total graph of cycle.

Making use of \(q\)-derivative operator, in this paper, we introduce new subclasses of the function class & of normalized analytic and bi-starlike functions defined in the open disk \(\mathbb{U}\). Furthermore, we find estimates on the first two Taylor-Maclaurin coefficients \(|a_2|\) and \(|a_3|\). Moreover, we obtain Fekete-Szegö inequalities for the new function classes.

A set \(S\) of vertices in a graph \(G\) is called a dominating set of \(G\) if every vertex in \(V(G)\S\) is adjacent to some vertex in \(S\). A set S is said to be a power dominating set of \(G\) if every vertex in the system is monitored by the set \(S\) following a set of rules for power system monitoring. A zero forcing set of \(G\) is a subset of vertices B such that if the vertices in \(B\) are colored blue and the remaining vertices are colored white initially, repeated application of the color change rule can color all vertices of \(G\) blue. The power domination number and the zero forcing number of G are the minimum cardinality of a power dominating set and the minimum cardinality of a zero forcing set respectively of \(G\). In this paper, we obtain the power domination number, total power domination number, zero forcing number and total forcing number for m-rooted sibling trees, l-sibling trees and I-binary trees. We also solve power domination number for circular ladder, Möbius ladder, and extended cycle-of-ladder.

A proper vertex coloring of a graph where every node of the graph dominates all nodes of some color class is called the dominator coloring of the graph. The least number of colors used in the dominator coloring of a graph is called the dominator coloring number denoted by \(X_d(G)\). The dominator coloring number and domination number of central, middle, total and line graph of quadrilateral snake graph are derived and the relation between them are expressed in this paper.

A digraph G is finite and is denoted as \(G(V,E)\) with \(V\) as set of nodes and E as set of directed arcs which is exact. If \((u, v)\) is an arc in a digraph \(D\), we say vertex u dominates vertex v. A special digraph arises in round robin tournaments. Tournaments with a special quality \(Q(n, k)\) have been studied by Ananchuen and Caccetta. Graham and Spencer defined tournament with \(q\) vertices
where \(q \equiv 3 (mod 4)\) is a prime. It was named suitably as Paley digraphs in respect deceased Raymond Paley, he was the person used quadratic residues to construct Hadamard matrices more than 50 years earlier. This article is based on a special class of graph called Paley digraph which admits odd edge graceful, super edge graceful and strong edge graceful labeling.

Molecular graphs are models of molecules in which atoms are represented by vertices and chemical bonds by edges of a graph. Graph invariant numbers reflecting certain structural features of a molecule that are derived from its molecular graph are known as topological indices. A topological index is a numerical descriptor of a molecule, based on a certain topological feature of the corresponding molecular graph. One of the most widely known topological descriptor is the Wiener index. The Weiner index \(w(G)\) of a graph G is defined as the half of the sum of the distances between every pair of vertices of \(G\). The construction and investigation of topological is one of the important directions in mathematical chemistry. The common neighborhood graph of G is denoted by con(\(G\)) has the same vertex set as G, and two vertices of con(\(G\)) are adjacent if they have a common neighbor in \(G\). In this paper we investigate the Wiener index of \(Y-tree,\, X-tree,\, con(Y-tree)\) and \(con(X-tree)\).

In the field of membrane computing. P system is a versatile model of computing, introduced by Paun [6], based on a combination of (i) the biological features of functioning of living cells and the members structure and (ii) the theoretical  concepts and results related to formal language theory. Among different Application areas of the model of P system, Ceterchi et al. [2] proposed an array-rewriting P system generating picture arrays based on the well-established notions in the area of array rewriting grammars and iso-array grammar have also been introduced. In this paper we consider structures in the two-dimensional plane called equi-triangular array composed of equilateral triangular array grammar and a corresponding P system, in the order to generate such structures. We Also examine the generative power of these new models of picture generation.

We disprove a conjecture proposed in [Gaspers et al., Discrete Applied Mathematics, 2010] and provide a new upper bound for the minimum number of brushes required to continually parallel clean a clique.

The strong chromatic index \( \chi’_s(G) \) of a graph \( G \) is the smallest integer \( k \) such that \( G \) has a proper edge \( k \)-coloring with the condition that any two edges at distance at most 2 receive distinct colors. It is known that \( \chi’_s(G) \leq 3\Delta – 2 \) for any \( K_4 \)-minor free graph \( G \) with \( \Delta \geq 3 \). We give a polynomial algorithm in order \( O(|E(G)|(n\Delta^2 + 2n + 14\Delta)) \) to strong color the edges of a \( K_4 \)-minor free graph with \( 3\Delta – 2 \) colors where \( \Delta \geq 3 \).

We introduce a new representation of MOFS of type \( F(m\lambda; \lambda) \), as a linear combination of \( \{0,1\} \) arrays. We use this representation to give an elementary proof of the classical upper bound, together with a structural constraint on a set of MOFS achieving the upper bound. We then use this representation to establish a maximality criterion for a set of MOFS of type \( F(m\lambda; \lambda) \) when \( m \) is even and \( \lambda \) is odd, which simplifies and extends a previous analysis \cite{ref3} of the case when \( m = 2 \) and \( \lambda \) is odd.

Arboricity is a graph parameter akin to chromatic number, in that it seeks to partition the vertices into the smallest number of sparse subgraphs. Where for the chromatic number we are partitioning the vertices into independent sets, for the arboricity we want to partition the vertices into cycle-free subsets (i.e., forests). Arboricity is NP-hard in general, and our focus is on the arboricity of cographs. For arboricity two, we obtain the complete list of minimal cograph obstructions. These minimal obstructions do generalize to higher arboricities; however, we no longer have a complete list, and in fact, the number of minimal cograph obstructions grows exponentially with arboricity.

We obtain bounds on their size and the height of their cotrees. More generally, we consider the following common generalization of colouring and partition into forests: given non-negative integers \( p \) and \( q \), we ask if a given cograph \( G \) admits a vertex partition into \( p \) forests and \( q \) independent sets. We give a polynomial-time dynamic programming algorithm for this problem. In fact, the algorithm solves a more general problem which also includes several other problems such as finding a maximum \( q \)-colourable subgraph, maximum subgraph of arboricity-\( p \), minimum feedback vertex set and the minimum weight of a \( q \)-colourable feedback vertex set.

Motivated by problems involving triangle-decompositions of graphs, we examine the facet structure of the cone \( \tau_n \) of weighted graphs on \( n \) vertices generated by triangles. Our results include enumeration of facets for small \( n \), a construction producing facets of \( \tau_{n+1} \) from facets of \( \tau_n \), and an arithmetic condition on entries of the normal vectors. We also point out that a copy of \( \tau_n \) essentially appears via the perimeter inequalities at one vertex of the metric polytope.

We consider the problem of detecting an intruder in a network where there are two types of detecting devices available. One device can determine the distance from itself to the intruder and the other can see the vertex it occupies as well as all adjacent vertices. The problem is to determine how many devices are required and where they should be placed in order to determine a single intruder’s location. We show that on the one hand, finding the minimum number of devices required to do this is easy when the network is a tree with at most one leaf adjacent to any vertex, while on the other hand finding this number is an NP-complete problem even for trees with at most two leaves adjacent to any vertex.

We present a 2-edge-coloured analogue of the duality theorem for transitive tournaments and directed paths. Given a 2-edge-coloured path \( P \) whose edges alternate blue and red, we construct a 2-edge-coloured graph \( D \) so that for any 2-edge-coloured graph \( G \),

\[
P \to G \iff G \not\to D.
\]

The duals are simple to construct, in particular \(|V(D)| = |V(P)| -1.\)

An edge coloring \( c \) of a graph \( G \) is a royal \( k \)-edge coloring of \( G \) if the edges of \( G \) are assigned nonempty subsets of the set \( \{1,2,\dots,k\} \) in such a way that the vertex coloring obtained by assigning the union of the colors of the incident edges of each vertex is a proper vertex coloring. If the vertex coloring is vertex-distinguishing, then \( c \) is a strong royal \( k \)-edge coloring. The minimum positive integer \( k \) for which \( G \) has a strong royal \( k \)-edge coloring is the strong royal index of \( G \). It has been conjectured that if \( G \) is a connected graph of order \( n \geq 4 \) where \( 2^{k-1} \leq n \leq 2^k – 1 \) for a positive integer \( k \), then the strong royal index of \( G \) is either \( k \) or \( k+1 \). We discuss this conjecture along with other information concerning strong royal colorings of graphs. A sufficient condition for such a graph to have strong royal index \( k+1 \) is presented.

Let \( k \) be a positive integer, and \( G \) be a \( k \)-connected graph. An edge-coloured path is rainbow if all of its edges have distinct colours. The rainbow \( k \)-connection number of \( G \), denoted by \( rc_k(G) \), is the minimum number of colours in an edge-colouring of \( G \) such that, any two vertices are connected by \( k \) internally vertex-disjoint rainbow paths. The function \( rc_k(G) \) was introduced by Chartrand, Johns, McKeon, and Zhang in 2009, and has since attracted significant interest. Let \( t_k(n,r) \) denote the minimum number of edges in a \( k \)-connected graph \( G \) on \( n \) vertices with \( rc_k(G) \leq r \). Let \( s_k(n,r) \) denote the maximum number of edges in a \( k \)-connected graph \( G \) on \( n \) vertices with \( rc_k(G) \geq r \). The functions \( t_1(n,r) \) and \( s_1(n,r) \) have previously been studied by various authors. In this paper, we study the functions \( t_2(n,r) \) and \( s_2(n,r) \). We determine bounds for \( t_2(n,r) \) which imply that \( t_2(n,2) = (1 + o(1)) n \log_2 n \), and \( t_2(n,r) \) is linear in \( n \) for \( r \geq 3 \). We also provide some remarks about the function \( s_2(n,r) \).

A signed graph \( (G, \sigma) \) is a graph \( G \) together with a mapping \( \sigma \) which assigns to each edge of \( G \) a sign, either positive or negative. The sign of a closed walk in \( (G, \sigma) \) is the product of the signs of its edges (considering multiplicity). Considering signs of closed walks as one of the key structures of signed graphs, a homomorphism of a signed graph \( (G, \sigma) \) to a signed graph \( (H, \pi) \) is defined to be a mapping that maps vertices to vertices, edges to edges, and that preserves incidences, adjacencies, and signs of closed walks. This is a recently defined notion, closely related to sign-preserving homomorphisms of signed graphs (or, equivalently, to homomorphisms of 2-edge-colored graphs), that helps, in particular, to establish a stronger connection between the theories of coloring and homomorphisms of graphs and the minor theory of graphs.

When there exists a homomorphism of \( (G, \sigma) \) to \( (H, \pi) \), one may write \( (G, \sigma) \to (H, \pi) \), thus extending the graph homomorphism order to a partial order on the classes of homomorphically equivalent signed graphs. In this work, studying this order, we prove that this order forms a lattice. That is to say, for each pair \( (G_1, \sigma_1) \) and \( (G_2, \sigma_2) \) of signed graphs, representing their respective classes, both their join and meet exist. While proving this result, we also show the existence of categorical products for signed graphs.

The game of cops and robbers on a graph is a vertex pursuit game played by two players with perfect information. Per the rules of the game, a given graph is either inherently cop-win or robber-win. It is possible that adding any edge changes the inherent nature of a particular graph. Such a graph is maximal in the sense that no edge can be added without changing its “win-state”. Furthermore, if deleting any edge changes the “win-state”, then this graph is minimal. Join us as we walk this thin blue line between cop-win and robber-win and explore the good, the bad, and the ugly.

Let \( H \) be a hypergraph of order \( n_H = |V(H)| \) and size \( m_H = |E(H)| \). The transversal number \( \tau(H) \) of a hypergraph \( H \) is the minimum number of vertices that intersect every edge of \( H \). A linear hypergraph is one in which every two distinct edges intersect in at most one vertex. A \( k \)-uniform hypergraph has all edges of size \( k \). For \( k \geq 2 \), let \( \mathcal{L}_k \) denote the class of \( k \)-uniform linear hypergraphs. We consider the problem of determining the best possible constants \( q_k \) (which depends only on \( k \)) such that \( \tau(H) \leq q_k(n_H + m_H) \) for all \( H \in \mathcal{L}_k \). It is known that \( q_2 = \frac{1}{3} \) and \( q_3 = \frac{1}{4} \). In this paper we show that \( q_4 = \frac{1}{5} \), which is better than for non-linear hypergraphs. Using the affine plane \( AG(2,4) \) of order 4, we show there are a large number of densities of hypergraphs \( H \in \mathcal{L}_4 \) such that \( \tau(H) = \frac{1}{5} (n_H + m_H) \).

Let \( F \) be a (possibly improper) edge-coloring of a graph \( G \); a vertex coloring of \( G \) is adapted to \( F \) if no color appears at the same time on an edge and on its two endpoints. If for some integer \( k \), a graph \( G \) is such that given any list assignment \( L \) to the vertices of \( G \), with \( |L(v)| \geq k \) for all \( v \), and any edge-coloring \( F \) of \( G \), \( G \) admits a coloring \( c \) adapted to \( F \) where \( c(v) \in L(v) \) for all \( v \), then \( G \) is said to be adaptably k-choosable. A \((k,d)\)-list assignment for a graph \( G \) is a map that assigns to each vertex \( v \) a list \( L(v) \) of at least \( k \) colors such that \( |L(x) \cap L(y)| \leq d \) whenever \( x \) and \( y \) are adjacent. A graph is \((k,d)\)-choosable if for every \((k,d)\)-list assignment \( L \) there is an \( L \)-coloring of \( G \). It has been conjectured that planar graphs are \((3,1)\)-choosable. We give some progress on this conjecture by giving sufficient conditions for a planar graph to be adaptably 3-choosable. Since \((k,1)\)-choosability is a special case of adaptable \( k \)-choosability, this implies that a planar graph satisfying these conditions is \((3,1)\)-choosable.

A broadcast on a nontrivial connected graph \( G = (V,E) \) is a function \( f : V \to \{0,1,\dots,\operatorname{diam}(G)\} \) such that \( f(v) \leq e(v) \) (the eccentricity of \( v \)) for all \( v \in V \). The weight of \( f \) is \( \sigma(f) = \sum_{v \in V} f(v) \). A vertex \( u \) hears \( f \) from \( v \) if \( f(v) > 0 \) and \( d(u,v) \leq f(v) \). A broadcast \( f \) is independent, or hearing independent, if no vertex \( u \) with \( f(u) > 0 \) hears \( f \) from any other vertex \( v \). We define a different type of independent broadcast, namely a boundary independent broadcast, as a broadcast \( f \) such that, if a vertex \( w \) hears \( f \) from vertices \( v_1, \dots, v_k \), \( k \geq 2 \), then \( d(w,v_i) = f(v_i) \) for each \( i \). The maximum weights of a hearing independent broadcast and a boundary independent broadcast are the \textit{hearing independence broadcast number} \( \alpha_h(G) \) and the boundary independence broadcast number \( \alpha_{bn}(G) \), respectively.

We prove that \( \alpha_{bn}(G) = \alpha(G) \) (the independence number) for any 2-connected bipartite graph \( G \) and that \( \alpha_{bn}(G) \leq n – 1 \) for all graphs \( G \) of order \( n \), characterizing graphs for which equality holds. We compare \( \alpha_{bn} \) and \( \alpha_h \) and prove that although the difference \( \alpha_h – \alpha_{bn} \) can be arbitrary, the ratio is bounded, namely \( \alpha_h / \alpha_{bn} < 2 \), which is asymptotically best possible. We deduce that \( \alpha_h(G) \leq 2n – 5 \) for all connected graphs \( G \neq P_n \) of order \( n \), which improves an existing upper bound for \( \alpha_h(G) \) when \( \alpha(G) \geq n/2 \).

We continue our studies of burn-off chip-firing games from Discrete Math. Theor. Comput. Sci. 15 (2013), no. 1, 121–132; MR3040546] and Australas. J. Combin. 68 (2017), no. 3, 330–345; MR3656659]. The latter article introduced randomness by choosing successive seeds uniformly from the vertex set of a graph \( G \). The length of a game is the number of vertices that fire (by sending a chip to each neighbor and annihilating one chip) as an excited chip configuration passes to a relaxed state. This article determines the probability distribution of the game length in a long sequence of burn-off games. Our main results give exact counts for the number of pairs \( (C, v) \), with \( C \) a relaxed legal configuration and \( v \) a seed, corresponding to each possible length. In support, we give our own proof of the well-known equicardinality of the set \( R \) of relaxed legal configurations on \( G \) and the set of spanning trees in the cone \( G^* \) of \( G \). We present an algorithmic, bijective proof of this correspondence.

We study homomorphism properties of signed \( K_4 \)-minor-free graphs. On the one hand, we give a necessary and sufficient condition for a signed graph \( B \) to admit a homomorphism from any signed \( K_4 \)-minor-free graph and we determine the smallest of all such signed graphs. On the other hand, we characterize the minimal cores that do not belong to the class of signed \( K_4 \)-minor-free graphs. This, in particular, gives a classification of odd-\( K_4 \)’s that are cores. Furthermore, we show some applications of our work.

Game coloring is a two-player game in which each player properly colors one vertex of a graph at a time until all the vertices are colored. An “eternal” version of game coloring is introduced in this paper in which the vertices are colored and re-colored from over a sequence of rounds. In a given round, each vertex is colored, or re-colored, once, so that a proper coloring is maintained. Player 1 wants to maintain a proper coloring forever, while player 2 wants to force the coloring process to fail. The eternal game chromatic number of a graph \( G \) is defined to be the minimum number of colors needed in the color set so that player 1 can always win the game on \( G \). The goal of this paper is to introduce this problem, consider several variations of this game, show its behavior on some elementary classes of graphs, and make some conjectures.

Let \( G \) be a graph with vertex set \( V \) and no isolated vertices. A subset \( S \subseteq V \) is a semipaired dominating set of \( G \) if every vertex in \( V \setminus S \) is adjacent to a vertex in \( S \) and \( S \) can be partitioned into two-element subsets such that the vertices in each subset are at most distance two apart. We present a method of building trees having a unique minimum semipaired dominating set.

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.