{
  "id": "2107.13806",
  "version": "v1",
  "published": "2021-07-29T08:10:35.000Z",
  "updated": "2021-07-29T08:10:35.000Z",
  "title": "The feasability problem for line graphs",
  "authors": [
    "Yair Caro",
    "Josef Lauri",
    "Christina Zarb"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-07-29T08:10:35.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C76"
    ],
    "keywords": [
      "line graph",
      "feasability problem",
      "minimum/maximum non-feasible pairs problem",
      "minimum/maximum value",
      "main results"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}