Complementary vanishing graphs Erickson, Craig; Gan, Luyining; Kritschgau, Jürgen ...
Linear algebra and its applications,
07/2024, Letnik:
692
Journal Article
Recenzirano
Odprti dostop
Given a graph G with vertices {v1,…,vn}, we define S(G) to be the set of symmetric matrices A=ai,j such that for i≠j we have ai,j≠0 if and only if vivj∈E(G). Motivated by the Graph Complement ...Conjecture, we say that a graph G is complementary vanishing if there exist matrices A∈S(G) and B∈S(G‾) such that AB=O. We provide combinatorial conditions for when a graph is or is not complementary vanishing, and we characterize which graphs are complementary vanishing in terms of certain minimal complementary vanishing graphs. In addition to this, we determine which graphs on at most 8 vertices are complementary vanishing.
Let G be a simple graph with n(G) vertices and e(G) edges. The elementary cyclic number c(G) of G is defined as c(G)=e(G)−n(G)+ω(G), where ω(G) is the number of connected components of G. The nullity ...of G, denoted by η(G), is the multiplicity of the eigenvalue zero of the adjacency matrix of G. A graph is leaf-free if it has no pendent vertices. In Ma et al. (2016) proved that if G is leaf-free and each component of G contains at least two vertices, then η(G)≤2c(G), the equality is attained if and only if G is the union of disjoint cycles, where each cycle has length a multiple of 4. In this paper, we completely characterize all leaf-free graphs with nullity one less than the above upper bound, i.e., η(G)=2c(G)−1.
Abstract The objective of this paper is to demonstrate that the joint treatment of the rescission and the relative nullity in the 20th title of 4th book of the chilean Civil Code is no way an ...accident or a mistake. On the contrary, that situation has an unnotice historical explanation in the origins of called laesio enormis.
Resumen El objetivo de este trabajo es demostrar que el tratamiento conjunto de la rescisión y la nulidad relativa en el título xx del libro iv del Código Civil no obedece a un error atribuible a Andrés Bello. Al contrario, dicho tratamiento tiene una explicación histórica, que surge -de modo solapado y que, por lo mismo, ha pasado casi inadvertida- en el origen mismo de la regulación de la rescisión por lesión.
Let G be a undirected graph without loops and multiple edges. By η(G),θ(G) and p(G) we respectively denote the nullity, the dimension of cycle space, and the number of pendant vertices of G. If each ...component of G contains at least two vertices, then it is proved that η(G)≤2θ(G)+p(G), the equality is attained if and only if every component of G is a cycle with size a multiple of 4.
The nullity of a vertex-weighted graph is equal to the number of zero eigenvalues of its adjacency matrix. In this article, we give a linear time algorithm to calculate the nullity of vertex-weighted ...block graphs, i.e., graphs in which every block is a clique, with weights assigned to the vertices.
This paper presents strong connections between four variants of the zero forcing number and four variants of the Grundy domination number. These connections bridge the domination problem and the ...minimum rank problem, providing a linear algebra approach to the domination problem. We show that several Grundy domination type parameters are bounded above by minimum rank type parameters. We also give a method to calculate the L-Grundy domination number by the Grundy total domination number, giving some linear algebra bounds for the L-Grundy domination number.
The Aα matrix of a graph G is defined by Nikiforov as Aα(G)=αD(G)+(1−α)A(G), where α∈0,1, A(G) and D(G) respectively denotes the adjacency matrix and the degree diagonal matrix of G. The eigenvalues ...of Aα(G) are called the Aα-eigenvalues of G. In this paper, we prove that, for a connected graph G of order n and with maximum degree Δ≥2 and for any α∈0,1), the multiplicity of an arbitrary Aα-eigenvalue λ of G, which is denoted as mα(G,λ), is bounded bymα(G,λ)≤(Δ−2)n+2Δ−1, the equality holds if and only if G and λ satisfy one of the following conditions:
(i) G=Kn with n≥3 and λ=αn−1;
(ii) G=Cn with even order, and λ∈{2α+2(1−α)cos2πjn:j=1,2,…,n−22};
(iii) G=Cn with odd order, and λ∈{2α+2(1−α)cos2πjn:j=1,2,…,n−12};
(iv) G=Kn2,n2 with n≥4, and λ=αn2.
Applying this result, we solve an open conjecture posed by Zhou et al. in 32 one year ago.
Given a simple graph G, let A(G) be its adjacency matrix and α′(G) be its matching number. The rank of G, written as r(G), refers to the rank of A(G). In this paper, some relations between the rank ...and the matching number of a graph are studied. Firstly, it is proved that −2d(G)⩽r(G)−2α′(G)⩽No, where d(G) and No are, respectively, the dimension of cycle space and the number of odd cycles of G. Secondly, sharp lower bounds on both r(G)−α′(G) and r(G)/α′(G) are determined. All the corresponding extremal graphs are characterized, respectively.
Let G be a simple undirected graph. Let 0≤α≤1. LetAα(G)=αD(G)+(1−α)A(G) where D(G) and A(G) are the diagonal matrix of the vertex degrees of G and the adjacency matrix of G, respectively. Let p(G)>0 ...and q(G) be the number of pendant vertices and quasi-pendant vertices of G, respectively. Let mG(α) be the multiplicity of α as an eigenvalue of Aα(G). It is proved thatmG(α)≥p(G)−q(G) with equality if each internal vertex is a quasi-pendant vertex. If there is at least one internal vertex which is not a quasi-pendant vertex, the equalitymG(α)=p(G)−q(G)+mN(α) is determined in which mN(α) is the multiplicity of α as an eigenvalue of the matrix N. This matrix is obtained from Aα(G) taking the entries corresponding to the internal vertices which are non quasi-pendant vertices. These results are applied to search for the multiplicity of α as an eigenvalue of Aα(G) when G is a path, a caterpillar, a circular caterpillar, a generalized Bethe tree or a Bethe tree. For the Bethe tree case, a simple formula for the nullity is given.
The nullity of a graph G, denoted by η(G), is the multiplicity of eigenvalue zero of the adjacency matrix of G. A graph is singular (resp., nonsingular) if η(G)≥1 (resp., if η(G)=0). A cycle-spliced ...graph is a cactus in which every block is a cycle. Recently, Singh et al. 16 consider the singularity of graphs in which every block is a clique. In this paper, we consider the nullity and the singularity of cycle-spliced graphs. Let G be a cycle-spliced graph with c(G) cycles. If G is bipartite, we prove that 0≤η(G)≤c(G)+1, the extremal graphs G with nullity 0 or c(G)+1 are respectively characterized. If all cycles in G are odd, we obtain the following two results: (i) G is nonsingular if c(G) is odd, and η(G) is 0 or 1 if c(G) is even. (ii) If every cycle in G has at most two cut-vertices of G, then G is singular if and only if c(G) is even and G contains half the cycles of order equal to 3(mod4) and half the cycles of order equal to 1(mod4).
PDF
