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 references
      0 references
      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

      Identifiers