Tuesday, 11 September 2007

What is known about the kmathrmth powers of graphs of diameter k+1?

Let G be a simple unweighted graph. The distance between two vertices u,v in G is the length of a shortest path in G between u and v. The diameter of G, denoted diam(G), is the largest distance between two vertices in G. For a natural number k, The kmathrmth power of G, denoted Gk, is the graph obtained from G by adding edges between every two vertices u,v where the distance between u,v in G is at most k.




Let mathcalFk be the family of all graphs that are the kmathrmth powers of graphs of diameter k+1. That is,




mathcalFk=Gkmiddiam(G)=k+1





mathcalF1 is the set of all graphs of diameter 2, and for all kge2, mathcalFksubseteqmathcalF2.



Is something more known about the structure of the graphs in mathcalFk for kge2? In particular, are these containments strict? Do we get more structure the higher the value of k?



Thanks for any ideas, pointers, and/or references on this.

No comments:

Post a Comment