Using p-row graphs to study p-competition graphs

MaRDI QIDQ6319409zbMATH OpenFDO

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

Publication date 27 May 2019

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)

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.

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)