2019/05/27 by Soogang Eoh, Eoh, Soogang, Taehee Hong +5
Computer Science · Mathematics · #05C05 #05C38 #05C62 #05C75 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.1905.10966
openalex publication_date 2019/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.