{
  "id": "1905.10966",
  "version": "v1",
  "published": "2019-05-27T04:06:46.000Z",
  "updated": "2019-05-27T04:06:46.000Z",
  "title": "Using $p$-row graphs to study $p$-competition graphs",
  "authors": [
    "Soogang Eoh",
    "Taehee Hong",
    "Suh-Ryung Kim",
    "Seung Chul Lee"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "For a positive integer $p$, the $p$-competition graph of a digraph $D$ is a graph which has the same vertex set as $D$ and an edge between distinct vertices $x$ and $y$ if and only if $x$ and $y$ have at least $p$ common out-neighbors in $D$. A graph is said to be a $p$-competition graph if it is the $p$-competition graph of a digraph. Given a graph $G$, we call the set of positive integers $p$ such that $G$ is a $p$-competition the competition-realizer of a graph $G$. In this paper, we introduce the notion of $p$-row graph of a matrix which generalizes the existing notion of row graph. We call the graph obtained from a graph $G$ by identifying each pair of adjacent vertices which share the same closed neighborhood the condensation of $G$. Using the notions of $p$-row graph and condensation of a graph, we study competition-realizers for various graphs to extend results given by Kim {\\it et al.}~[$p$-competition graphs, {\\it Linear Algebra Appl.} {\\bf 217} (1995) 167--178]. Especially, we find all the elements in the competition-realizer for each caterpillar.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-05-27T04:06:46.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C05",
      "05C38",
      "05C62",
      "05C75"
    ],
    "keywords": [
      "competition graph",
      "row graph",
      "positive integer",
      "linear algebra appl",
      "vertex set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}