We say that a graph \(G\) has a path-system with respect to a set \(W\) of even number of vertices in \(G\) if \(G\) has vertex-disjoint paths \(P_1,P_2, \ldots, P_m\) such that (i) each path \(P_i\) connects two vertices of \(W\) and (ii) the set of end-vertices of the paths \(P_i\) is exactly \(W\). In particular, \(m=|W|/2\). Moreover, if \(G\) has a path-system with respect to every set \(W\) of even number of vertices in \(G\), we say that \(G\) has a path system. We prove the following theorems: (i) if \(G\) is an \(r\)-edge-connected \(r\)-regular graph, then for any \(r-1\) edges \(e_1,\ldots, e_{r-1}\), \(G-\{e_1,\ldots, e_{r-1}\}\) has a path-system, (ii) every \(k\)-connected \(K_{1,k+1}\)-free graph has a path-system, and (iii) if a connected bipartite graph \(G\) with bipartition \((A,B)\) satisfies \(|A| \le 2|B|\), \(|N_G(X)| \ge 2|X|\) or \(N_G(X)=B\) for all \(X\subseteq A\), and \(|N_G(Y)| \ge |Y|\) or \(N_G(Y)=A\) for all \(Y\subseteq B\), then \(G\) has a path-system with respect to every set \(W\) of even number of vertices of \(A\).

For a graph \(G\), an Italian dominating function (IDF) is a function \(f: V(G) \rightarrow \{0,1,2\}\) such that all vertices labeled with 0 must have at least two neighbors assigned the label 1 or at least one neighbor assigned the label 2. The weight of \(f\), denoted by \(w(f)\), is calculated by summing all the labels assigned by the function. Let \(f\) be an IDF on \(G\) with a minimum weight, denoted as \(\gamma_I(G)\). If \(S\) is the set of vertices where \(f(v) > 0\), then an Inverse Italian Dominating Function (IIDF) \(f'\) is defined as an IDF on \(G\) such that \(f'(v) = 0\) for all \(v \in S\). The notation \(\gamma_{iI}(G)\) represents the Inverse Italian Domination Number of the graph \(G\), which is the minimum weight among all IIDFs on \(G\). In this paper, we find \(\gamma_{iI}(G)\) of graphs and characterize the graphs for which \(\gamma_I(G) = 2\) and \(3\), as well as those with \(\gamma_{iI}(G) = 2\) and \(3\). Additionally, we provide a characterization of trees and graphs that achieve the largest possible \(\gamma_{iI}(G)\).

The strongly chordal graph literature has recently expanded to include the sequentially smaller classes of \(s\)-strongly chordal graphs for \(s = 1, 2, 3,\ldots\) (and the limiting class of majorly chordal graphs). These stronger classes preserve — while simultaneously intensifying —  the conventional chords-of-cycles inspiration of chordal graph theory. This leads to characterizing corresponding \(s\)-strongly chordal bipartite graphs and majorly chordal bipartite graphs. Our new analysis does this by using chains of quadrangles, with each adjacent pair of quadrangles having a unique edge in common. This leads to constructive characterizations that exploit a somewhat unexpected resemblance to earlier characterizations of \(s\)-strongly chordal graphs involving chains of triangles sharing common edges to characterize \(s\)-strongly chordal tripartite (and, similarly, multipartite) graphs.

In this paper, we present a method for constructing a new sequence, which we call \(k-\)division sequence and denoted by \(h_n(k)\). Using Fibonacci and Pell sequences, we define the \(k-\)division Fibonacci-Pell sequence obtain its properties, and prove that this sequence is periodic. Then, as an application of the sequence, we define \(1-\)division Fibonacci-Pell sequence on finite groups and study it in the groups \(G_m\) and \(H_{(u,l,m)}\) groups.

We consider the minimum weight and smallest weight minimum-size dominating set problems in vertex-weighted graphs and networks. The latter problem is a two-objective optimization problem, which is different from the classic minimum weight dominating set problem that requires finding a dominating set of the smallest weight in a graph without trying to optimize its cardinality. In other words, the objective of minimizing the size of the dominating set in the two-objective problem can be considered as a constraint, i.e. a particular case of finding Pareto-optimal solutions. First, we show how to reduce the two-objective optimization problem to the minimum weight dominating set problem by using Integer Linear Programming formulations. Then, under different assumptions, the probabilistic method is applied to obtain upper bounds on the minimum weight dominating sets in graphs. The corresponding randomized algorithms for finding small-weight dominating sets in graphs are described as well. Computational experiments are used to illustrate the results for two different types of random graphs.

Let \(G\) be a plane graph. If two edges are adjacent and consecutive on the boundary walk of a face of \(G\), then they are said to be facially adjacent. We call \(G\) facially entire \(k\)-colorable if there is a mapping from \(V(G)\cup E(G)\cup F(G)\) to a \(k\) color set so that any two facially adjacent edges, adjacent vertices, adjacent faces, and incident elements receive different colors. The facial entire chromatic number of \(G\) is defined to be the smallest integer \(k\) such that \(G\) is facially entire \(k\)-colorable. In 2016, Fabrici, Jendrol’ and Vrbjarová conjectured that every connected, loopless, bridgeless plane graph is facially entire \(7\)-colorable. In this paper, we give a positive answer to this conjecture for \(K_4\)-minor-free graphs. More specifically, we shall prove that every \(K_{4}\)-minor-free graph is facially entire \(7\)-colorable.

The Markov graph of a self-map on a combinatorial tree is a directed graph that encodes the covering relations between edges of the tree under the map. This work explores the dynamical structure of self-maps on trees with weakly connected Markov graphs. The main result of the paper is a complete characterization of self-maps on finite sets that yield weakly connected Markov graphs for all trees. Additionally, we describe the dynamical structure of self-maps whose Markov graphs take specific forms, including complete digraphs, cycles, paths, in-stars, and out-stars.

In this paper, we construct two infinite families of graphs \(G(d,c)\) and \(G^+(d,c)\), where, in both cases, a vertex label is \(x_1x_2\ldots x_c\) with \(x_i\in\{1,2,\ldots, d\}\). We provide a tight lower bound on the metric dimension of \(G^+(d, c)\). Moreover, we give the definition and properties of the supertoken graphs, a generalization of the well-known token graphs. Finally, we provide an upper bound on the metric dimension of supertoken graphs.

Let \(A\) be a commutative ring with nonzero identity and \(n\geq 2\) be a positive integer. With the ring \(R=A\times\cdots\times A\) (\(n\) times), one can associate graphs \(TD(R)\) and \(ZD(R)\) respectively called the total dot product graph and the zero-divisor dot product graph of \(R\). In this paper, we study some topological properties of these two dot product graphs of \(R.\) In particular, it is shown that, the zero-divisor dot product graph \(ZD(R)\) is a projective graph if and only if \(R\) is isomorphic to \(\frac{Z_2\left[x\right]}{\left\langle x^2+x+1\right\rangle}\times\frac{Z_2\left[x\right]}{\left\langle x^2+x+1\right\rangle}.\) Moreover, we prove that no total dot product graph can be projective. With these observations, we classify all commutative rings for which dot product graphs \(ZD(R)\) and \(TD(R)\) have crosscap two.

Some methods of decomposing \(v(=mn)\times b\) incidence matrix of regular group divisible (RGD) designs into square submatrices of order \(m\) are described. Such designs are known as tactical decomposable designs. As a by–product, resolvable solutions of some RGD designs are obtained. A relationship between tactical decomposable designs and \(\left(2,\ n\right)-\)threshold schemes is also given.