A Nordhaus‐Gaddum‐type result for the induced path number

A Nordhaus‐Gaddum‐type result for the induced path number

0.00 Avg rating0 Votes
Article ID: iaor20125708
Volume: 24
Issue: 3
Start Page Number: 329
End Page Number: 338
Publication Date: Oct 2012
Journal: Journal of Combinatorial Optimization
Authors: , , ,
Keywords: matrices
Abstract:

The induced path number ρ(G) of a graph G is defined as the minimum number of subsets into which the vertex set of G can be partitioned so that each subset induces a graph. A Nordhaus‐Gaddum‐type result is a (tight) lower or upper bound on the sum (or product) of a parameter of a graph and its complement. If G is a subgraph of H, then the graph HE(G) is the complement of G relative to H. In this paper, we consider Nordhaus‐Gaddum‐type results for the parameter ρ when the relative complement is taken with respect to the complete bipartite graph K n,n .

Reviews

Required fields are marked *. Your email address will not be published.