Graph representing the edges of a multigraph
Dans cet article nous donnons diverses caractérisations des graphes représentatifs des arêtes d'un multigraphe (line graph of a multigraph). La caractérisation essentielle est formulée en termes d'exclusion de 7 sous-graphes. La démonstration utilise la caractérisation des graphes représentatifs de arêtes d'un graphe simple due à \textit{L. W. Beineke} [J. Comb. Theory 9, 129--135 (1970; Zbl 0202.55702)]. Les autres caractérisations sont données en termes de cliques (généralisation du théorème de \textit{J. Krausz} [Mat. Fiz. Lapok 50, 75--85 (1943; Zbl 0061.41401)] et de cliques maximales.
- Complexity of representation of graphs by set systems
- Polyhedral characterizations and perfection of line graphs
- Clique family inequalities for the stable set polytope of quasi-line graphs.
- Line graphs and forbidden induced subgraphs
- Every 3-connected \(\{K_{1,3},N_{1,2,3}\}\)-free graph is Hamilton-connected
- Local clique covering of claw-free graphs
- Dominoes
- A closure for Hamilton-connectedness in \(\{K_{1,3}, \Gamma_3\}\)-free graphs
- Every 3-connected \(\{K_{1, 3}, \Gamma_3\}\)-free graph is Hamilton-connected
- Correcting a graph into a linegraph minimizing Hamming distance edition is NP-complete and FPT by treewidth
This page was built for publication: Graph representing the edges of a multigraph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2546881)