scientific article; zbMATH DE number 1334630
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.
- The super line graph \({\mathfrak L}_2\)
- The line completion number of hypercubes
- The spectra of super line multigraphs
- A number theoretic problem on super line graphs
- scientific article; zbMATH DE number 617584 (Why is no real title available?)
- Line completion number of grid graph \(P_n\times P_m\)
- A survey of line digraphs and generalizations
- New results and open problems in line graphs
- Some parameters of restricted super line graphs
- Super point graph and point completion number
- Path-comprehensive and vertex-pancyclic properties of super line graph L₂(G)
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4262240)
