A number theoretic problem on super line graphs
| Autor: | Jay S. Bagga, Badri N. Varma, Lowell W. Beineke |
|---|---|
| Jazyk: | angličtina |
| Předmět: |
Discrete mathematics
Super line graph lcsh:Mathematics 010102 general mathematics Line graph 0102 computer and information sciences lcsh:QA1-939 01 natural sciences law.invention Combinatorics 010201 computation theory & mathematics Graph power law Petersen graph Discrete Mathematics and Combinatorics Graph homomorphism Bound graph Crossing number (graph theory) Graph toughness 0101 mathematics Complement graph Line completion number Mathematics |
| Zdroj: | AKCE International Journal of Graphs and Combinatorics, Vol 13, Iss 2, Pp 177-190 (2016) |
| ISSN: | 0972-8600 |
| DOI: | 10.1016/j.akcej.2016.05.001 |
| Popis: | In Bagga et al. (1995) a generalization of the line graph concept was introduced. Given a graph G with at least r edges, the super line graph of index r , L r ( G ) , has as its vertices the sets of r edges of G , with two adjacent if there is an edge in one set adjacent to an edge in the other set. The line completion number lc ( G ) of a graph G is the least index r for which L r ( G ) is complete. In this paper we investigate the line completion number of K m , n . This turns out to be an interesting optimization problem in number theory, with results depending on the parities of m and n . If m ≤ n and m is a fixed even number, then lc ( K m , n ) has been found for all even values of n and for all but finitely many odd values. However, when m is odd, the exact value of lc ( K m , n ) has been found in relatively few cases, and the main results concern lower bounds for the parameter. Thus, the general problem is still open, with about half of the cases unsettled. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|