scientific article; zbMATH DE number 2230916
The induced path number \(\rho(G)\) of a graph \(G\) is defined as the minimum number of subsets into which the vertex set \(V(G)\) of \(G\) can be partitioned such that each subset induces a path. This paper investigates the induced path number of the complement of the Cartesian product of two complete graphs \(K_m\) and \(K_n\), the complement of the path \(P_n\), \(n\geq4\), the cycle \(C_{n-1}\), \(n\geq4\), the graph \(C_m\times C_n\), \(m\geq n\geq3\), and the graph \(C_3\times P_m\), for \(m\geq4\). The following beautiful result of Nordhaus and Gaddum type for the induced path number of a graph and its complement is proved as well. Theorem: For any graph \(G\) of order \(n\) we have \[ \sqrt n\leq\rho(G)+\rho(\overline{G})\leq\biggl\lceil\frac{3n}2\biggr\rceil. \] Moreover both bounds are tight.
- Nordhaus-Gaddum results for the sum of the induced path number of a graph and its complement
- Product Nordhaus-Gaddum-type results for the induced path number involving complements with respect to \(K_n\) or \(K_{n,n}\)
- Nordhaus-Gaddum results for the induced path number of a graph when neither the graph nor its complement contains isolates
- Nordhaus-Gaddum type results for the induced path number with relative complements in \(K_{m,n}\)
- A Nordhaus-Gaddum-type result for the induced path number
- A Nordhaus-Gaddum-type result for the induced path number
- Nordhaus-Gaddum results for the sum of the induced path number of a graph and its complement
- Product Nordhaus-Gaddum-type results for the induced path number involving complements with respect to \(K_n\) or \(K_{n,n}\)
- Nordhaus-Gaddum results for the induced path number of a graph when neither the graph nor its complement contains isolates
- The induced path number of the Cartesian product of some graphs
- scientific article; zbMATH DE number 1161374 (Why is no real title available?)
- scientific article; zbMATH DE number 889959 (Why is no real title available?)
- Induced cycle path number of derived graphs
- Nordhaus-Gaddum type results for the induced path number with relative complements in \(K_{m,n}\)
- The influence of the addition or deletion of a vertex or an edge on the induced path number of a graph
- Induced path factors of regular graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5708983)