Maximum nullity and zero forcing number on cubic graphs

2017/05/27 by Saieed Akbari, Akbari, Saieed, Ebrahim Vatandoost +3
Computer Science · Mathematics · #05C07 #05C85 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.1705.09773

openalex publication_date 2017/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let G be a graph. The maximum nullity of G, denoted by M(G), is defined to be the largest possible nullity over all real symmetric matrices A whose a_ij≠ 0 for i≠ j, whenever two vertices u_i and u_j of G are adjacent. In this paper, we characterize all cubic graphs with zero forcing number 3. As a corollary, it is shown that if the zero forcing number is 3, then M(G)=3. In addition, we introduce a family of cubic graphs containing graphs G with M(G)=Z(G)=4. Also, we provide an algorithm which make a relation between maximum nullity of G and the number of leaves in a spanning tree of G.

Related

• Techniques for determining equality of the maximum nullity and the zero\n forcing number of a graph
• Maximum Nullity and Forcing Number on Graphs with Maximum Degree at most Three
• Zero Forcing Sets for Graphs
• The Classification of Graphs on 8 vertices with Coinciding Zero Forcing number and Maximum Nullity
• Zero forcing and maximum nullity for hypergraphs