scientific article; zbMATH DE number 2230916

From MaRDI portal
Publication:5708983





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.











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)