The Eigen-Cover Ratio of a Graph: Asymptotes, Domination and Areas

NEW

Problem: For a finite simple connected graph $G$ of order $n\ge3$, let

$$E(G)=\sum_i|\lambda_i|$$

be its graph energy. If $S$ is a minimum vertex cover and $H=G[S]$, define $\widehat E(H)=E(H)$, except that $\widehat E(H)=1$ when $H$ is edgeless. The paper’s eigen-cover ratio is

$$\rho(G,S)=\frac{|S|\,\widehat E(H)}{nE(G)}.$$

For a graph class $\mathcal F=(G_n)$, its eigen-cover area is obtained by integrating the ratio function in $n$, multiplied by average degree. The paper does not specify a unique real interpolation from integer orders; below I prove the natural repaired form, e.g. for the standard piecewise-linear interpolation used to make the integral rigorous.

Result: The complete graph is pointwise maximal for the eigen-cover ratio, hence it has maximal eigen-cover area under the natural interpolation convention.

Let $G$ be connected, non-complete, with $n\ge3$, and let $S$ be a minimum vertex cover. Since $H=G[S]$ is an induced subgraph, $A(H)$ is a principal submatrix of $A(G)$. Graph energy is the nuclear norm of the adjacency matrix, so

$$E(H)=\|A(H)\|_*\le \|A(G)\|_*=E(G).$$

If $H$ is edgeless, then $\widehat E(H)=1\le E(G)$, since connected $G$ contains an edge and thus $E(G)\ge E(K_2)=2$. Therefore always

$$\widehat E(H)\le E(G).$$

Because $G\neq K_n$, there are two nonadjacent vertices $u,v$. Then $V(G)\setminus\{u,v\}$ is a vertex cover, so

$$|S|\le n-2.$$

Thus

$$\rho(G,S)=\frac{|S|\widehat E(H)}{nE(G)} \le \frac{|S|}{n} \le \frac{n-2}{n}.$$

For $K_n$, a minimum vertex cover has size $n-1$, and its cover graph is $K_{n-1}$. Since $E(K_n)=2(n-1)$ and $E(K_{n-1})=2(n-2)$,

$$\rho(K_n)=\frac{(n-1)2(n-2)}{n\,2(n-1)} =\frac{n-2}{n}.$$

So $K_n$ maximizes the eigen-cover ratio at every order $n\ge3$.

For area, let $b(x)=(x-2)/x$. The piecewise-linear interpolation of any class ratio lies below the interpolation of $b(n)$, and since $b$ is concave on $[2,\infty)$, it lies below $b(x)$. Also $2m/n\le n-1$, with equality for $K_n$. Hence every class satisfies

$$A_{\mathcal F}(n)\le (n-1)\int_2^n \frac{x-2}{x}\,dx = (n-1)(n-2\log n+2\log2-2),$$

which is exactly the complete-graph area computed in the paper.

Citation: Definitions and conjecture: P. A. Winter and C. L. Jessop, “The Eigen-Cover Ratio of a Graph: Asymptotes, Domination and Areas,” viXra:1503.0148. No prior published proof is invoked here.