1. Nordhaus-Gaddum Results for the Induced Path Number of a Graph When Neither the Graph Nor Its Complement Contains Isolates.
- Author
-
Hattingh, J., Saleh, O., Merwe, L., and Walters, T.
- Subjects
- *
GRAPHIC methods , *GRAPH theory , *SUBSET selection , *SET theory , *ISOLATED systems (Thermodynamics) - Abstract
The induced path number $$\rho (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 path. A product Nordhaus-Gaddum-type result is a bound on the product of a parameter of a graph and its complement. Hattingh et al. (Util Math 94:275-285, ) showed that if G is a graph of order n, then $$\lceil \frac{n}{4} \rceil \le \rho (G) \rho (\overline{G}) \le n \lceil \frac{n}{2} \rceil $$ , where these bounds are best possible. It was also noted that the upper bound is achieved when either G or $$\overline{G}$$ is a graph consisting of n isolated vertices. In this paper, we determine best possible upper and lower bounds for $$\rho (G) \rho (\overline{G})$$ when either both G and $$\overline{G}$$ are connected or neither G nor $$\overline{G}$$ has isolated vertices. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF