t-Strong cliques and the degree-diameter problem

Investor logo

Warning

This publication doesn't include Institute of Computer Science. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

SLESZYNSKA-NOWAK Malgorzata DĘBSKI Michał Karol

Year of publication 2019
Type Article in Periodical
Magazine / Source Acta Mathematica Universitatis Comenianae
MU Faculty or unit

Faculty of Informatics

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:

You are running an old browser version. We recommend updating your browser to its latest version.

More info