Let \(G\) be a graph with vertex set \(V(G) = \{v_1, v_2, \dots, v_n\}\). We associate to \(G\), a matrix \(P(G)\) whose \((i, j)\)-th entry is the maximum number of vertex-disjoint paths between the corresponding vertices if \(i\neq j\), and is zero otherwise. We call this matrix the path matrix of \(G\), and its eigenvalues are referred to as the path eigenvalues of \(G\). In this paper, we investigate the path eigenvalues of graphs resulting from certain graph operations and specific graph families.

Null graphs (respectively, 1-regular graphs) are the only regular graphs with local antimagic chromatic number 1 (respectively, undefined). In this paper, we proved that the join of 1-regular graph and a null graph has local antimagic chromatic number 3. As a by-product, we also obtained many families of (possibly disconnected or regular) bipartite and tripartite graph with local antimagic chromatic number 3.

Let \(G = (V, E)\) be a graph with vertex set \(V\) and edge set \(E\). A vertex set \(S \subset V\) is a perfect dominating set if every vertex in \(V – S\) is adjacent to exactly one vertex in \(S\). A perfect dominating set \(S\) is furthermore: (i) an efficient dominating set or a \(1\)-efficient dominating set if no two vertices in \(S\) are adjacent, (ii) a total efficient dominating set or a \(2\)-efficient dominating set if every vertex in \(S\) is adjacent to exactly one other vertex in \(S\), and (iii) a \(1,2\)-efficient dominating set if every vertex in \(S\) either adjacent to no vertices in \(S\) or to exactly one other vertex in \(S\). In this paper we introduce the concept of \(1,2\)-efficiency in graphs and apply it to the existence of \(1,2\)-efficient sets in grid graphs \(G_{m,n}\), that is, graphs resembling chessboards having a rectangular array of \(m \times n\) vertices arranged into \(m\) rows of \(n\) vertices, or \(n\) columns of \(m\) vertices. It is well known that almost no grid graphs are \(1\)-efficient, and relatively few grid graphs are \(2\)-efficient. However, in this paper, we show that all but a relatively small percentage of grid graphs are \(1,2\)-efficient.

onsidering regions in a map to be adjacent when they have nonempty intersection (as opposed to the traditional view requiring intersection in a linear segment) leads to the concept of a facially complete graph: a plane graph that becomes complete when edges are added between every two vertices that lie on a face. Here we present a complete catalog of facially complete graphs: they fall into seven types. A consequence is that if \(q\) is the size of the largest face in a plane graph \(G\) that is facially complete, then \(G\) has at most \(\left\lfloor 3q/2\right\rfloor\) vertices. This bound was known, but our proof is completely different from the 1998 approach of Chen, Grigni, and Papadimitriou (Planar map graphs, Proc. 30th ACM Symp. Th. of Computing, 514–523). Our method also yields a count of the 2-connected facially complete graphs with \(n\) vertices. We also show that if a plane graph has at most two faces of size 4 and no larger face, then the addition of both diagonals to each 4-face leads to a graph that is 5-colorable.

A bowtie graph is the union of two edge disjoint 3-cycles which share a single vertex. A mixed bowtie is a partial orientation of a bowtie graph. In this paper, we consider decompositions of the complete mixed graph into mixed bowties consisting of a union of two isomorphic copies of mixed triples.

In this paper, we study the signless Laplacian eigenvalues of the subgraph \(Z^*(\Gamma(\mathbb{Z}_n))\) of the total graph of the integers modulo \(n\), \(\mathbb{Z}_n\), for certain values of \(n\). We also identify specific values of \(n\) for which the graph is \(Q\)-integral. Finally, we discuss the normalized Laplacian spectrum of \(Z^*(\Gamma(\mathbb{Z}_n))\).

We obtain several results towards the proof that the necessary conditions are sufficient for the existence of a GDD\((n_1 = 1, n_2 = n, 4; \lambda_1, \lambda_2)\) where \(\lambda_1 \ge \lambda_2\). We also have some general results including the constructions for larger block sizes as well as when the first group size \(n_1\) is not 1 or \(\lambda_1 < \lambda_2\).

We introduce a new arc in directed graphs of integers. Our arcs are determined by the values of the popular arithmetic functions such as the divisor function \(\tau\), the prime divisors counting functions \(\omega\) and \(\Omega\), and the sum of digits function \(s_b\), evaluated at the multiples \(N\) of a particular integer. Among other things, we determine the positive integers that have arcs to all except a finite number of positive integers. We also propose some possible research problems at the end of this article.

Let \(G\) be a plane graph with vertex, edge, and region sets \(V(G), E(G), F(G)\) respectively. A zonal labeling of a plane graph \(G\) is a labeling \(\ell: V(G)\rightarrow \{1,2\}\subset \mathbb{Z}_3\) such that for every region \(R\in F(G)\) with boundary \(B_R\), \(\sum\limits_{v\in V(B_R)}\ell(v)=0\) in \(\mathbb{Z}_3\). We extend this to general abelian groups, defining a \(\Gamma\)-zonal labeling as a labeling \(\ell:V(G)\rightarrow \Gamma\setminus \{0\}\) such that for every region \(R\in F(G)\), \(\sum\limits_{v \in V(B_R)}\ell(v)\) is \(0\). We explore existence of \(\Gamma\)-zonal labelings for various families of graphs. We also introduce two variations: generative and strong \(\Gamma\)-zonal labelings. A generative \(\Gamma\)-zonal labeling is one in which the elements used to label the vertices generate the group \(\Gamma\). A strong \(\Gamma\)-zonal labeling is a labeling in which the additive order of \(\ell(v)\) is equal to \(\deg(v).\) Examples and existence results are provided for both variations. It is shown that strong \(\Gamma\)-zonal labelings have a connection to edge colorings that generalizes the connection between zonal labelings and proper edge \(3\)-colorings of cubic maps.

In this paper, \(k\)-domination is considered for the king’s, queen’s, knight’s, and bishop’s graphs for square boards of any dimension size. We also consider \(k\)-tuple total domination for the queen’s and bishop’s graphs for square boards as well.

Finite games in normal form and their mixed extensions are a corner stone of noncooperative game theory. Often  generic finite games and their mixed extensions are considered. But the properties which one expects in generic games and the existence of games with these properties are often treated only in passing. The paper considers strong properties and proves that generic games have these properties. The space of mixed strategy combinations is embedded in a natural way into a product of real projective spaces. All relevant hypersurfaces extend to this bigger space. The paper shows that for all games in the complement of a semialgebraic subset of codimension at least one all relevant hypersurfaces in the bigger space are smooth and maximally transversal. The proof uses the theorem of Sard and follows an argument of Khovanskii.

A proper \(k\)-coloring \(\alpha\) of a graph \(G\) induces a partition \(\Pi = \{C_1, C_2, \dots, C_k\}\), where \(C_i = \{v \in V(G) \mid \alpha(v) = i\}\). The color code of a vertex \(v \in V(G)\) with respect to \(\Pi\) is defined as the tuple \(c_{\Pi}(v) = (d(v, C_1), d(v, C_2), \dots, d(v, C_k))\), where \(d(v, C_i)\) represents the distance from \(v\) to the set \(C_i\). A proper \(k\)-coloring \(\alpha\) is called a locating \(k\)-coloring of \(G\) if \(\alpha\) induces a partition \(\Pi\) such that for any two distinct vertices \(u, v \in V(G)\), it holds that \(c_{\Pi}(u) \neq c_{\Pi}(v)\). The locating chromatic number of \(G\), denoted \(\chi_L(G)\), is the smallest \(k\) for which a locating \(k\)-coloring of \(G\) exists. In this paper, we establish a connection between the locating \(k\)-coloring of \(C_n(1,2,\dots,t) + K_m\) and the union of graphs \(\bigcup_{i=1}^p C_{n_i} + K_m\), leveraging properties of simple cycles in directed graphs. Using this connection, we determine the locating chromatic number of \(C_n(1,2,\dots,t) + K_m\) for \(t = 2\) and \(n \in [6, 28]\), as well as for \(t = 3\) and \(n \in [8, 24]\).

We characterize line digraphs of polytrees, including several of their well-known subclasses. For a given undirected tree, we characterize its orientations with weak line digraphs, and count the exact number. Furthermore, we find the minimum, maximum, and average sizes of these line digraphs. We provide an explicit formula for the number of weak components in line digraphs of polytrees in terms of the inner sources and sinks. Additionally, we count the average number of weak components in them among all orientations of a fixed tree. Finally, we propose an algorithm for finding weak components in line digraphs of polytrees.