Using p-row graphs to study p-competition graphs

arXiv1905.10966MaRDI QIDQ6319409FDOQ6319409

Authors: Soogang Eoh, Taehee Hong, Suh-Ryung Kim, Seung-Chul Lee 

Publication date: 27 May 2019

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.} {�f 217} (1995) 167--178]. Especially, we find all the elements in the competition-realizer for each caterpillar.

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)

This page was built for publication: Using $p$-row graphs to study $p$-competition graphs

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