Equitable edge partitions and Kirchhoff graphs

The relationship between Kirchhoff graphs and equitable edge partitions of their corresponding digraphs is discussed. It is shown that if the natural edge partition for the associated digraph to a vector graph is equitable and the quotient matrix based on this partition is symmetric, then the vector...

Full description

Saved in:
Bibliographic Details
Published in:Linear algebra and its applications 2022-04, Vol.639, p.225-242
Main Authors: Reese, Tyler M., Fehribach, Joseph D., Paffenroth, Randy C.
Format: Article
Language:English
Subjects:
Digraphs
Equitable edge partitions
Graph theory
Graphs
Kirchhoff graphs
Linear algebra
Mathematical analysis
Matrices (mathematics)
Partitions (mathematics)
Quotients
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The relationship between Kirchhoff graphs and equitable edge partitions of their corresponding digraphs is discussed. It is shown that if the natural edge partition for the associated digraph to a vector graph is equitable and the quotient matrix based on this partition is symmetric, then the vector graph is Kirchhoff. The converse is not true: many Kirchhoff graphs have natural edge partitions that are not equitable. In addition, it is shown that for a digraph with an equitable edge partition, the partition is uniform if and only if the quotient matrix is symmetric. Hence every uniform equitable edge partition of a digraph is a Kirchhoff partition and can generate a Kirchhoff graph.
ISSN:0024-3795
1873-1856
DOI:10.1016/j.laa.2022.01.008