Nordhaus–Gaddum Results for the Induced Path Number of a Graph When Neither the Graph Nor Its Complement Contains Isolates
| Autor: | Ossama A. Saleh, Terry J. Walters, Johannes H. Hattingh, Lucas C. van der Merwe |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Discrete mathematics
Induced path 010102 general mathematics 0102 computer and information sciences 01 natural sciences Upper and lower bounds Graph Theoretical Computer Science Vertex (geometry) Combinatorics 010201 computation theory & mathematics Discrete Mathematics and Combinatorics 0101 mathematics Mathematics |
| Zdroj: | Graphs and Combinatorics. 32:987-996 |
| ISSN: | 1435-5914 0911-0119 |
| DOI: | 10.1007/s00373-015-1629-z |
| Popis: | The induced path number $$\rho (G)$$?(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, 2014) 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 $$?n4?≤?(G)?(G¯)≤n?n2?, where these bounds are best possible. It was also noted that the upper bound is achieved when either G or $$\overline{G}$$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})$$?(G)?(G¯) when either both G and $$\overline{G}$$G¯ are connected or neither G nor $$\overline{G}$$G¯ has isolated vertices. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink