t-Strong cliques and the degree-diameter problem
| Authors | |
|---|---|
| Year of publication | 2019 |
| Type | Article in Periodical |
| Magazine / Source | Acta Mathematica Universitatis Comenianae |
| MU Faculty or unit | |
| Citation | |
| Web | http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1258/762 |
| Keywords | strong edge-coloring; strong clique |
| Attached files | |
| Description | For a graph G, L(G)(t) is the t-th power of the line graph of G that is, vertices of L(G)(t) are edges of G and two edges e, f is an element of E(G) are adjacent in L(G)(t) if G contains a path with at most t vertices that starts in a vertex of e and ends in a vertex of f. The t-strong chromatic index of G is the chromatic number of L(G)(t) and a t-strong clique in G is a clique in L(G)(t). Finding upper bounds for the t-strong chromatic index and t-strong clique are problems related to two famous problems: the conjecture of Erdos and NeAetfil concerning the strong chromatic index and the degree/diameter problem. We prove that the size of a t-strong clique in a graph with maximum degree Delta is at most 1.75 Delta(t) + O (Delta t(-1)), and for bipartite graphs the upper bound is at most Delta(t) + O (Delta t(-1)). We also show results for some special classes of graphs: K-1,K-r-free graphs and graphs with a large girth. |
| Related projects: |