Campus Units

Mathematics

Document Type

Article

Publication Version

Accepted Manuscript

Publication Date

6-18-2012

Journal or Book Title

Journal of Graph Theory

Volume

72

First Page

146

Last Page

177

DOI

10.1002/jgt.21637

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 a manuscript of an article from Journal of Graph Theory 72 (2012): 146, doi:10.1002/jgt.21637. Posted with permission.

Copyright Owner

Wiley Periodicals, Inc.

Language

en

File Format

application/pdf

Published Version

Share

COinS