The competition number of a generalized line graph is at most two

Boram Park; Yoshio Sano

doi:10.46298/dmtcs.575

Article

The competition number of a generalized line graph is at most two

Boram Park⁽¹⁾, Yoshio Sano⁽²⁾

(1) Center for Discrete Mathematics and Theoretical Computer Science [Rutgers]

(2) National Institute of Informatics

Download article

Open on HAL

Imported on

October 12, 2011

Published on

August 4, 2012

Last modified on

March 31, 2025

Volume 14

vol. 14:2

Graph Theory

DOI

10.46298/dmtcs.575

License

https://about.hal.science/hal-authorisation-v1

Indicators

804

Views

3325

Downloads

The competition number of a generalized line graph is at most two

Boram Park⁽¹⁾, Yoshio Sano⁽²⁾

(1) Center for Discrete Mathematics and Theoretical Computer Science [Rutgers]

(2) National Institute of Informatics

Abstract

In 1982, Opsut showed that the competition number of a line graph is at most two and gave a necessary and sufficient condition for the competition number of a line graph being one. In this paper, we generalize this result to the competition numbers of generalized line graphs, that is, we show that the competition number of a generalized line graph is at most two, and give necessary conditions and sufficient conditions for the competition number of a generalized line graph being one.

Keywords