Parameters Related to Tree-Width, Zero Forcing, and Maximum Nullity of a Graph

Thumbnail Image
Date
2013-02-01
Authors
Barioli, Francesco
Barrett, Wayne
Fallat, Shaun
Hogben, Leslie
Shader, Bryan
van den Driessche, P.
van der Holst, Hein
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Organizational Unit
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Electrical and Computer EngineeringMathematics
Abstract

Tree-width, and variants that restrict the allowable tree decompositions, play an important role in the study of graph algorithms and have application to computer science. The zero forcing number is used to study the maximum nullity/minimum rank of the family of symmetric matrices described by a graph. We establish relationships between these parameters, including several Colin de Verdière type parameters, and introduce numerous variations, including the minor monotone floors and ceilings of some of these parameters. This leads to new graph parameters and to new characterizations of existing graph parameters. In particular, tree-width, largeur d'arborescence, path-width, and proper path-width are each characterized in terms of a minor monotone floor of a certain zero forcing parameter defined by a color change rule.

Comments

This is the peer-reviewed version of the following article: Barioli, Francesco, Wayne Barrett, Shaun M. Fallat, H. Tracy Hall, Leslie Hogben, Bryan Shader, Pauline van den Driessche, and Hein Van Der Holst. "Parameters Related to Tree‐Width, Zero Forcing, and Maximum Nullity of a Graph." Journal of Graph Theory 72, no. 2 (2013): 146-177, which has been published in final form at DOI: 10.1002/jgt.21637. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Self-Archiving. Posted with permission.

Description
Keywords
Citation
DOI
Copyright
Sun Jan 01 00:00:00 UTC 2012
Collections