The feasibility problem for line graphs

DOI10.1016/J.DAM.2022.09.019MaRDI QIDQ2097181zbMATH OpenOpenAlexFDO

Authors Yair Caro, Josef Lauri, Christina Zarb

Publication date 11 November 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2107.13806

zbMATH Keywords

feasibilityline graphs

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76)

Abstract: We consider the following feasibility problem: given an integer $ngeq1$ and an integer $m$ such that $$, does there exist a line graph $L=L(G)$ with exactly $n$ vertices and $m$ edges ? We say that a pair $(n,m)$ is non-feasible if there exists no line graph $L(G)$ on $n$ vertices and $m$ edges, otherwise we say $(n,m)$ is a feasible pair. Our main result shows that for fixed $ngeq5$, the values of $m$ for which $(n,m)$ is a non-feasible pair, form disjoint blocks of consecutive integers which we completely determine. On the other hand we prove, among other things, that for the more general family of claw-free graphs (with no induced $K_{1,3}$-free subgraph), all $(n,m)$-pairs in the range $$ are feasible pairs.

Recommendations

• Ramsey numbers for line graphs
• Forbidden induced subgraphs for line graphs
• Minimal claw-free graphs
• A solution to a problem of Jacobson, Kézdy and Lehel
• The structure of claw-free graphs

Cites work

• Characterizations of derived graphs
• Claw-free graphs---a survey
• Forbidden induced subgraphs for line graphs
• Graph classes characterized both by forbidden subgraphs and degree sequences
• scientific article; zbMATH DE number 3461962 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Index of parameters of iterated line graphs
• Induced subgraphs of given sizes
• Line graphs and forbidden induced subgraphs
• On Sums of Triangular Numbers and Sums of Squares
• The history of degenerate (bipartite) extremal graph problems
• The sum of the squares of the parts of a partition, and some related questions

Cited in

(3)

• Flip colouring of graphs
• Avoiding intersections of given size in finite affine spaces \(\operatorname{AG}(n,2)\)
• The feasibility problem: the family \(\mathcal{F}(G)\) of all induced \(G\)-free graphs.

This page was built for publication: The feasibility problem for line graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2097181)