American Journal of Combinatorics

The nullity of the net Laplacian matrix of a signed graph

Zhuang Xiong — Wed, 24 Jan 2024 00:00:00 +0000

The net Laplacian matrix of a signed graph \(\Gamma = (G, \sigma)\), where \(G = (V(G),E(G))\) is an unsigned graph (referred to as the underlying graph) and \(\sigma: E(G) \rightarrow \{-1, +1\}\) is the sign function, is defined as \(L^{\pm}(\Gamma) = D^{\pm}(\Gamma) - A(\Gamma)\). Here, \(D^{\pm}(\Gamma)\) and \(A(\Gamma)\) represent the diagonal matrix of net-degrees and the adjacency matrix of \(\Gamma\), respectively. The nullity of \(L^{\pm}(\Gamma)\), denoted as \(\eta (L^{\pm} (\Gamma))\), refers to the multiplicity of \(0\) as an eigenvalue of \(L^{\pm}(\Gamma)\). In this paper, we concentrate on the nullity of the net Laplacian matrix of a connected signed graph \(\Gamma\), and establish that \(1 \leq \eta (L^{\pm} (\Gamma)) \leq \min\{ \beta(\Gamma) + 1, |V(\Gamma)| - 1 \}\), where \(\beta(\Gamma) = |E(\Gamma)| - |V(\Gamma)| + 1\) denotes the cyclomatic number of \(\Gamma\). We completely determine the connected signed graphs with nullity \(|V(\Gamma)| - 1\). Additionally, we characterize the signed cactus graphs with nullity \(1\) or \(\beta(\Gamma) + 1\).

On the Min4PC Matrix of a Tree

Ali Azimi, Rakesh Jana, Mukesh Nagar, Sivaramakrishnan Sivasubramanian — Wed, 14 Feb 2024 00:00:00 +0000

The Four point condition (abbreviated as 4PC) is a condition used to test if a given distance matrix arises from shortest path distances on trees. From a tree \(T\), Bapat and Sivasubramanian defined a matrix \(\operatorname{Min4PC}_T\) based on this condition. They also gave a basis \(B\) for the row space of \(\operatorname{Min4PC}_T\) and determined its Smith Normal Form. In this paper, we consider the matrix \(\operatorname{Min4PC}_T[B,B]\) restricted to a basis \(B\) and give an explicit inverse for it. It is known that the distance matrix \(D_T\) of a tree \(T\), is invertible and that its inverse is a rank-one update of its scaled Laplacian. Our inverse has a similar form and is a rank-one update of a Laplacian like matrix.

Computing the degree of some matchings in a graph

Rosário Fernandes — Sun, 06 Oct 2024 00:00:00 +0000

Let \(G\) be a connected graph. A matching \(M\) in \(G\) is a set of edges of \(G\) without two of them adjacent (having a common vertex). The graph whose vertices are the matchings in \(G\) and two matchings \(M\) and \(N\) are adjacent if and only if \( (M\setminus N)\cup (N\setminus M)\) is the edge set of a path or a cycle, is denoted by \({\cal G}({\cal M}(G))\) and called the skeleton of the matching polytope of \(G\). The degree of a matching \(M\) in \(G\) is the degree of the vertex \(M\) in \({\cal G}({\cal M}(G))\). In the literature some authors have studied the degree of some matchings, in particular when \(G\) is a tree. In this paper we continue this study and we present some formulas to compute the degree of a matching \(M\) in a graph with cycles. More explicitly, we focus on the matchings having \(1\) or \(2\) edges and on the matchings of more than two edges with some constraints.

Computing the permanental polynomial of 4k-intercyclic bipartite graphs

Ravindra Bapat, Ranveer Singh, Hitesh Wankhede — Wed, 20 Nov 2024 00:00:00 +0000

Let \(G\) be a bipartite graph with adjacency matrix \(A(G)\). The characteristic polynomial \(\phi(G,x)=\det(xI-A(G))\) and the permanental polynomial \(\pi(G,x) = \operatorname{per}(xI-A(G))\) are both graph invariants used to distinguish graphs. For bipartite graphs, we define the modified characteristic polynomial, which is obtained by changing the signs of some of the coefficients of \(\phi(G,x)\). For \(4k\)-intercyclic bipartite graphs, i.e., those for which the removal of any \(4k\)-cycle results in a \(C_{4k}\)-free graph, we provide an expression for \(\pi(G,x)\) in terms of the modified characteristic polynomial of the graph and its subgraphs. Our approach is purely combinatorial in contrast to the Pfaffian orientation method found in the literature to compute the permanental polynomial.

A note on the minimum rank of graphs with given dominating induced subgraph

Zoran Stanić — Wed, 11 Dec 2024 00:00:00 +0000

An induced subgraph of a graph \(G\) is said to be dominating if every vertex of \(G\) is at distance at most one from this subgraph. We investigate pairs \((G, F)\) where \(F\) is a non-singular dominating induced subgraph of \(G,\) and the rank of \(G\) (that is, the rank of its adjacency matrix) attains the minimum, i.e., equals the number of vertices in \(F\). It turns out that the inverse of the adjacency matrix of a non-singular path, half graph, or even cycle is the adjacency matrix of a related signed graph; here, a half graph refers to a connected chain graph with exactly one vertex in each cell. We exploit this property to give a complete characterization of graphs \(G\) paired with any of these graphs in the role of \(F\). The bipartite case is singled out. It occurs that every nonsingular \(F\) is paired with an infinite family of graphs \(G\), and their number is comparatively large even if we exclude the existence of the so-called twin vertices. The latter empirical observation is demonstrated through some examples.