Independence number and disjoint theta graphs (Q554004): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
| Property / review text | |||
Summary: The goal of this paper is to find vertex disjoint even cycles in graphs. For this purpose, define a \(\theta \)-graph to be a pair of vertices \(u, v\) with three internally disjoint paths joining \(u\) to \(v\). Given an independence number \(\alpha \) and a fixed integer \(k\), the results contained in this paper provide sharp bounds on the order \(f (k, \alpha )\) of a graph with independence number \(\alpha (G) \leq \alpha \) which contains no \(k\) disjoint \(\theta \)-graphs. Since every \(\theta \)-graph contains an even cycle, these results provide \(k\) disjoint even cycles in graphs of order at least \(f (k, \alpha ) + 1\). We also discuss the relationship between this problem and a generalized Ramsey problem involving sets of graphs. | |||
| Property / review text: Summary: The goal of this paper is to find vertex disjoint even cycles in graphs. For this purpose, define a \(\theta \)-graph to be a pair of vertices \(u, v\) with three internally disjoint paths joining \(u\) to \(v\). Given an independence number \(\alpha \) and a fixed integer \(k\), the results contained in this paper provide sharp bounds on the order \(f (k, \alpha )\) of a graph with independence number \(\alpha (G) \leq \alpha \) which contains no \(k\) disjoint \(\theta \)-graphs. Since every \(\theta \)-graph contains an even cycle, these results provide \(k\) disjoint even cycles in graphs of order at least \(f (k, \alpha ) + 1\). We also discuss the relationship between this problem and a generalized Ramsey problem involving sets of graphs. / rank | |||
Normal rank | |||
| Property / Mathematics Subject Classification ID | |||
| Property / Mathematics Subject Classification ID: 05C35 / rank | |||
Normal rank | |||
| Property / Mathematics Subject Classification ID | |||
| Property / Mathematics Subject Classification ID: 05C55 / rank | |||
Normal rank | |||
| Property / zbMATH DE Number | |||
| Property / zbMATH DE Number: 5933973 / rank | |||
Normal rank | |||
Revision as of 14:17, 1 July 2023
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Independence number and disjoint theta graphs |
scientific article |
Statements
Independence number and disjoint theta graphs (English)
0 references
29 July 2011
0 references
Summary: The goal of this paper is to find vertex disjoint even cycles in graphs. For this purpose, define a \(\theta \)-graph to be a pair of vertices \(u, v\) with three internally disjoint paths joining \(u\) to \(v\). Given an independence number \(\alpha \) and a fixed integer \(k\), the results contained in this paper provide sharp bounds on the order \(f (k, \alpha )\) of a graph with independence number \(\alpha (G) \leq \alpha \) which contains no \(k\) disjoint \(\theta \)-graphs. Since every \(\theta \)-graph contains an even cycle, these results provide \(k\) disjoint even cycles in graphs of order at least \(f (k, \alpha ) + 1\). We also discuss the relationship between this problem and a generalized Ramsey problem involving sets of graphs.
0 references
