The feasibility problem for line graphs

Abstract

We consider the following feasibility problem: given an integer n ≥ 1 and an integer m such that 0 ≤ m ≤ ( n/2 ) , 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 n ≥ 5, the values of m for which (n, m) is a non-feasible pair form disjoint blocks of consecutive integers which we determine completely. On the other hand we prove, among other things, that for the more general family of claw-free graphs (with no induced K1,3-free subgraph), all (n, m)-pairs in the range 0 ≤ m ≤ ( n/2 ) are feasible pairs