Namespaces
Variants
Actions

Difference between revisions of "Line graph"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (+ category)
 
Line 13: Line 13:
  
 
====References====
 
====References====
* Biggs, Norman ''Algebraic graph theory'' 2nd ed. Cambridge University Press (1994) ISBN 0-521-45897-8 {{ZBL|0797.05032}}
+
* Biggs, Norman ''Algebraic graph theory'' 2nd ed. Cambridge University Press (1994) {{ISBN|0-521-45897-8}} {{ZBL|0797.05032}}
* Cvetković, Dragoš; Rowlinson, Peter; Simić, Slobodan ''Spectral generalizations of line graphs. On graphs with least eigenvalue $−2$'' London Mathematical Society Lecture Note Series '''314''' Cambridge University Press(2004) ISBN 0-521-83663-8 {{ZBL|1061.05057}}
+
* Cvetković, Dragoš; Rowlinson, Peter; Simić, Slobodan ''Spectral generalizations of line graphs. On graphs with least eigenvalue $−2$'' London Mathematical Society Lecture Note Series '''314''' Cambridge University Press(2004) {{ISBN|0-521-83663-8}} {{ZBL|1061.05057}}
  
 
[[Category:Graph theory]]
 
[[Category:Graph theory]]

Latest revision as of 17:39, 11 November 2023

2020 Mathematics Subject Classification: Primary: 05C76 [MSN][ZBL]

of a graph $G$

The (unoriented) graph $L(G)$ having a vertex set in one-to-one correspondence with the edge set of $G$, and vertices adjacent in $L(G)$ if the corresponding edges in $G$ have exactly one vertex in common.

The spectra of line graphs have been investigated. Let $G$ have vertices $\{v_1,\ldots,v_n\}$ and edges $e_1,\ldots,e_p$, and let $M$ be the $n \times p$ incidence matrix of $G$, so that $M_{ij} = 1$ if $v_i$ is incident with edge $j$ and otherwise zero. The adjacency matrix $A_L$ of $L(G)$ satisfies $$ M^\top M = A_L + 2 I_p $$ where $I_p$ is an identity matrix. It follows that all eigenvalues of $A_L$ are $\ge -2$.


References

  • Biggs, Norman Algebraic graph theory 2nd ed. Cambridge University Press (1994) ISBN 0-521-45897-8 Zbl 0797.05032
  • Cvetković, Dragoš; Rowlinson, Peter; Simić, Slobodan Spectral generalizations of line graphs. On graphs with least eigenvalue $−2$ London Mathematical Society Lecture Note Series 314 Cambridge University Press(2004) ISBN 0-521-83663-8 Zbl 1061.05057
How to Cite This Entry:
Line graph. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Line_graph&oldid=54360