The feasability problem for line graphs

Yair Caro, Josef Lauri, Christina Zarb

Published 2021-07-29Version 1

Given $F$, a family of graphs, and a pair $(n,m)$, $n \geq 1$, $ 0 \leq m \leq \binom{n}{2}$, the pair $(n,m)$ is called \emph{feasible} (for $F$) if there is a graph $G \in F $, with $n$ vertices and $m$ edges. Otherwise $(n,m)$ is called an \emph{non-feasible} pair. A family of graphs $F$ is called feasible if for every $n \geq 1$, every pair $(n,m)$ with $ 0 \leq m \leq \binom{n}{2}$ is feasible, otherwise $F$ is called non-feasible. The minimum/maximum non-feasible pairs problem requires that, for a non-feasible family $F$, the minimum/maximum value of $m$ such that the pair $(n,m)$ is not feasible is determined for all values of $n$. We shall be identifying some feasible families of graphs such as $K_{1,3}$-free graphs, chordal graphs, and paw-free graphs. We shall focus on the study of families of lines graphs. We reserve the notation $( N,M)$ for a line graph $L(G)$ having $N$ vertices and $M$ edges to make a clear distinction from the underlying graph $G$ having $n$ vertices and $m$ edges where $m = N$. We give two main results. We determine, for line graphs with $N$ vertices, all non-feasible pairs $(N,M)$ as well as the minimum value of $M$ for which the pair $(N,M)$ is not feasible.