Premium
Vector representation of graph domination
Author(s) -
Zewi Noga
Publication year - 2012
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20606
Subject(s) - mathematics , domination analysis , combinatorics , conjecture , independence number , line graph , discrete mathematics , graph , upper and lower bounds , vertex (graph theory) , mathematical analysis
We study a function on graphs, denoted by “Gamma”, representing vectorially the domination number of a graph, in a way similar to that in which the Lovsz Theta function represents the independence number of a graph. This function is a lower bound on the homological connectivity of the independence complex of the graph, and hence is of value in studying matching problems by topological methods. Not much is known at present about the Gamma function, in particular, there is no known procedure for its computation for general graphs. In this article we compute the precise value of Gamma for trees and cycles, and to achieve this we prove new lower and upper bounds on Gamma, formulated in terms of known domination and algebraic parameters of the graph. We also use the Gamma function to prove a fractional version of a strengthening of Ryser's conjecture. © 2011 Wiley Periodicals, Inc. J Graph Theory