Cyclomatic numbers of connected induced subgraphs
type: Item
instance of: scholarly article
title: Cyclomatic numbers of connected induced subgraphs
zbMATH Open document ID: 0783.05065
DOI: 10.1016/0012-365X(92)90150-E
author: Xingxing Yu
published in: Discrete Mathematics
publication date: 1993-01-16T00:00:00Z
review text: 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.
reviewed by: Brian Alspach
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 94365
zbMATH Keywords: cyclomatic number
zbMATH Keywords: independent set
zbMATH Keywords: induced subgraphs
zbMATH Keywords: upper bounds
MaRDI profile type: Publication
cites work: Research problems
cites work: Q5422499
full work available at URL: 0012-365x(92)90150-e
OpenAlex ID: W2077257901
description: scientific article; zbMATH DE number 94365