On independent cycles and edges in graphs
type: Item
instance of: scholarly article
title: On independent cycles and edges in graphs
zbMATH Open document ID: 0844.05064
DOI: 10.1016/0012-365X(94)00275-N
published in: Discrete Mathematics
publication date: 1996-03-26T00:00:00Z
review text: Denote by \(\langle n\rangle\) the complete graph \(K_n\), by \(\langle p, q\rangle\) the complete bipartite graph \(K_{pq}\), and by \(\langle\langle p\rangle, q\rangle\) the graph obtained from \(\langle p, q\rangle\) by converting the \(p\)-vertex set to \(K_p\). For positive integers \(n\) and \(k\), let \(f(n, k)\) be the number of edges of the graph \(\langle\langle 2k- 1\rangle, n- 2k+ 1\rangle\) and \(g(n, k)\) the number of edges of the graph obtained from \(\langle 3k- 1\rangle\) by attaching \(n- 3k+ 1\) pendant edges. \textit{P. Justesen} [Ann. Discrete Math. 41, 299-305 (1989; Zbl 0673.05065)] proved that, for any integer \(k\geq 2\), if \(G\) is a graph on \(n\) vertices such that \(n\geq k\) and \[ e(G)\geq \max\{f(n, k), g(n, k)+ 1\}, \] then \(G\) contains \(k\) vertex-disjoint (``independent'') cycles or \(G\simeq \langle\langle 2k- 1\rangle, n- 2k+ 1\rangle\). Using Justesen's argument, the author extends his result by determining the corresponding extremal graphs, i.e., the graphs \(G\) with \(e(G)= \max\{f(n, k), g(n, k)\}\), which do not contain \(k\) independent cycles. A modification of the same proof leads to the solution of the following problem: For integers \(k\), \(s\) with \(0\leq s\leq k\) and \(k\geq 2\), let \({\mathcal G}(n, k, s)\) be the class of graphs on \(n\) vertices not containing \(k\) independent subgraphs of which \(k- 2\) are cycles and the rest \(K_2\)'s. Determine those graphs in \({\mathcal G}(n, k, s)\) with the maximum number of edges for \(n\geq 3k- s\).
reviewed by: Norman F. Quimpo
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 858119
zbMATH Keywords: extremal graphs
zbMATH Keywords: independent cycles
author: Thomas Andreae
MaRDI profile type: Publication
cites work: Q3852212
cites work: On the maximal number of independent circuits in a graph
cites work: On maximal paths and circuits of graphs
cites work: Q5342984
cites work: Q3826605
cites work: Q4775880
Recommended article: Q3855211
Recommended article: Graphs with large maximum degree containing no odd cycles of a given length
Recommended article: Maximal and maximum independent sets in graphs with at mostr cycles
Recommended article: Q4030535
Recommended article: Q3105531
Recommended article: Q3714106
Recommended article: The number of maximal independent sets in a connected graph
Recommended article: The second largest number of maximal independent sets in graphs with at most \(k\) cycles
Recommended article: On covering a bipartite graph with cycles
Recommended article: On the maximum number of independent cycles in a bipartite graph
description: scientific article; zbMATH DE number 858119