Recognizing Generating Subgraphs in Graphs without Cycles of Lengths 6 and 7

Abstract

Let $B$ be an induced complete bipartite subgraph of $G$ on vertex sets of bipartition $B_X$ and $B_Y$. The subgraph $B$ is {\it generating} if there exists an independent set $S$ such that each of $S\cup B_X$ and $S\cup B_Y$ is a maximal independent set in the graph. If $B$ is generating, it \textit{produces} the restriction $w(B_X)=w(B_Y)$. Let $w:V(G)⟶\mathbb{R}$ be a weight function. We say that $G$ is $w$-well-covered if all maximal independent sets are of the same weight. The graph $G$ is $w$-well-covered if and only if $w$ satisfies all restrictions produced by all generating subgraphs of $G$. Therefore, generating subgraphs play an important role in characterizing weighted well-covered graphs. It is an \textbf{NP}-complete problem to decide whether a subgraph is generating, even when the subgraph is isomorphic to $K_{1,1}$ \cite{bnz:related}. We present a polynomial algorithm for recognizing generating subgraphs for graphs without cycles of lengths 6 and 7.

13 pages, 3 figures