Metrics
84 Record Views
Journal article
Characterizing paths as m-step competition graphs
Discrete mathematics, Vol.310(19), pp.2555-2559
10/06/2010
Web of Science ID: WOS:000280945000012
Abstract
In 2000 Cho, Kim and Nam proved that P(n), the path on n vertices, is a 2-step competition graph for all n. In 2005, Helleloid proved that P(n) is an (n - 1)- and (n - 2)-step competition graph for all n and proved further that of all connected triangle-free graphs on n vertices, only the star is an m-step competition graph for m >= n. In this paper we show that if m divides n - 1 or n - 2, then P(n) is an m-step competition graph and that if n >= 6 and n/2 <= m <= n - 3, then P(n) is not an m-step competition graph. (C) 2010 Elsevier B.V. All rights reserved.
Related links
Details
- Title
- Characterizing paths as m-step competition graphs
- Publication Details
- Discrete mathematics, Vol.310(19), pp.2555-2559
- Resource Type
- Journal article
- Publisher
- Elsevier
- Grant note
- NSF; National Science Foundation (NSF)
- Copyright
- © 2010 Elsevier B.V. All rights reserved.
- Identifiers
- WOS:000280945000012; 99380468036506600
- Academic Unit
- Mathematics and Statistics; Hal Marcus College of Science and Engineering
- Language
- English