Parity Dimension for Graphs - A Linear Algebraic Approach

DOI10.1080/0308108021000049293MaRDI QIDQ4796507zbMATH OpenOpenAlexFDO

Authors Ashok T. Amin, Peter Slater, Guo-Hui Zhang

Publication date 17 March 2003

Published in Linear and Multilinear Algebra (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/0308108021000049293

zbMATH Keywords

adjacency matrix

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Matrices over special rings (quaternions, finite fields, etc.) (15B33)

Review text

Let \(A\) be the adjacency matrix of a graph \(G\) and \(I\) the identity matrix. The parity dimension \(\text{PD}(G)\) of \(G\) is the dimension of the null space of \(A+I\) over the two-element field \(Z_2\). Some properties of \(\text{PD}(G)\) for special classes of graphs \(G\) are studied, including the consideration of some upper bounds. \(\text{PD}(G)\) is related to dominating sets in \(G\).

Recommendations

• Parity dimension for graphs
• Counting all parity realizable trees
• scientific article; zbMATH DE number 3889564
• scientific article; zbMATH DE number 894703
• Publication:4943285

Cites work

• \(\sigma\)-Automata and Chebyshev-polynomials
• Characterizing switch-setting problems^∗
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• Inseparable orthogonal matrices over \(\mathbb{Z}_2\)
• Linear cellular automata and the garden-of-eden
• Parity dimension for graphs

Cited in

(11)

• Periodic harmonic functions on lattices and points count in positive characteristic
• Parity dimension for graphs
• Lights Out for graphs related to one another by constructions
• A group-labeling version of the Lights Out game
• Periodic binary harmonic functions on lattices
• Counting all parity realizable trees
• Random Lights Out processes on graphs
• Effects of edge addition or removal on the nullity of a graph
• Bounding the multiplicities of eigenvalues of graph matrices in terms of circuit rank
• Minimum light number of lit-only \(\sigma\)-game on a tree
• Combinatorial properties of a general domination problem with parity constraints

This page was built for publication: Parity Dimension for Graphs - A Linear Algebraic Approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4796507)