Cyclomatic numbers of connected induced subgraphs (Q1199496): Difference between revisions

For a graph \(G=\bigl( V(G),E(G) \bigr)\), the cyclomatic number \(cy(G)\) is defined by \(cy(G)=| E(G) |-| V(G) |+1\). Let \(A\) be an independent set of vertices of \(G\) and let \(C(A)\) be the collection of all connected induced subgraphs of \(G\) which contain \(A\). Define \(\omega(A)=\min \bigl\{ cy(H):H \in C(A) \bigr\}\). The author obtains upper bounds for \(\omega(A)\) over the class of graphs and over the class of triangle-free graphs. He also considers the edge version of the question and shows that all upper bounds are best possible.