Let be a simple unweighted graph. The distance between two vertices in is the length of a shortest path in between and . The diameter of , denoted , is the largest distance between two vertices in . For a natural number , The power of , denoted , is the graph obtained from by adding edges between every two vertices where the distance between in is at most .
Let be the family of all graphs that are the powers of graphs of diameter . That is,
is the set of all graphs of diameter , and for all , .
Is something more known about the structure of the graphs in for ? In particular, are these containments strict? Do we get more structure the higher the value of ?
Thanks for any ideas, pointers, and/or references on this.
No comments:
Post a Comment