No label defined (Q4262240)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1334630
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1334630 |
Statements
19 July 2000
0 references
super line graph
0 references
independence number
0 references
maximum independent set
0 references
0.8922692537307739
0 references
0.8310478329658508
0 references
The super line graph of index \(r\), denoted by \({\mathcal L}_r(G)\) is defined for any graph \(G\) with at least \(r\) edges. Its vertices are the sets of \(r\) edges of \(G\), and two such sets are adjacent if an edge of one is adjacent to an edge of the other. The authors prove the following results: (1) Let \(G\) be a graph with at least \(r\) edges. Then the independence number of \({\mathcal L}_r(G)\) is \(\alpha({\mathcal L}_r(G))= \left(\begin{smallmatrix} \alpha'(G)\\ r\end{smallmatrix}\right)\). Furthermore, if \(S\) is a maximum independent set of vertices in \({\mathcal L}_r(G)\), then either (i) \(S= \left(\begin{smallmatrix} X\\ r\end{smallmatrix}\right)\) for some maximum independent set \(X\) of edges of \(G\), or (ii) \(S\) consists of \(r+1\) disjoint stars \(K_{1,r}\), or (iii) \(r= 3\) and the vertices in \(S\) are \(K_{1,3}\)'s or \(K_3\)'s. (2) If \(G\) is a graph with no isolated edges, then the index-2 super line graph \({\mathcal L}_2(G)\) is vertex-pancyclic. The authors also raise some open questions.
0 references