On total matching numbers and total covering numbers of complementary graphs (Q1245240): Difference between revisions

A vertex \(u\) of a graph \(G\) is said to cover itself, all incident edges, and all adjacent vertices. An edge \(uv\) of \(G\) covers itself, \(u\) and \(v\), and all adjacent edges. A subset \(S\) of \(V(G)\cup E(G)\) is called a total cover if the elements of \(S\) cover \(G\). Two elements of \(V(G)\cup E(G)\) are said to be independent if neither covers the other. Define \(\alpha_2(G)=\min|S|\), where the min is taken over all total covers \(S\) of \(G\), and \(\beta_2(G)=\max|T|\) , where the max is taken over all subsets \(T\) of \(V(G)\cup E(G)\) whose elements are pairwise independent. The following theorems are presented. Theorem 1: If \(G\) is a graph on \(n\) vertices, then \[ 2\{n/2\}\leq\beta_2(G)+\beta_2(\overline G)\leq\{3n/2\}. \] The upper bound is best possible for all \(n\), the lower bound is best possible for all \(n\neq 2(\mod 4)\). Theorem 2: If \(G\) is a graph on \(n\) vertices, then \[ \{n/2\}+1\leq\alpha_2(G)+\alpha_2(\overline G)\leq\{3n/2\}. \] The upper bound is best possible for all \(n\), the lower bound is best possible for odd \(n\). Theorem 3: If \(G\) is a connected graph on \(n\geq 2\) vertices, then \[ \alpha_2(G)+\beta_2(G)\leq n+\{n/2\}/2. \] This bound is best possible.