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