math.stackexchange.com/questions/1722377/…

Are you referring to your first picture? Yes, that shows there is a difference in distance distribution and degree distribution. But can you show two 6-regular graphs with different distance distributions where one distribution (correctly) predicts something like contagion-spreading better than the other? If not, the branching factor of 6 is still going to be the main measure an epidemiologist will use to estimate a disease's r-naught value.

good luck! To address your question, clearly the distance distribution provides more information than a degree distribution, but can you find examples of when the distance distribution explains any phenomenon in real networks that the degree-distribution is insufficient to detect or predict? The distance distribution may provide more info, but at the cost of a more complex measure. There needs to be incentive to use a complex measure when a degree distribution would do.

To make a random partial k-tree:start with a large clique,store all cliques of size k, choose one uniformly at random and make a new node adj to that chosen k-clique.This creates a clique of size (k+1), so you store more new k-cliques. Now delete some small number of edges(this destroys a number of k-cliques). Again, add a new vertex adj to a uniformly-chosen existing k-clique and repeat. I have a paper on higher-order structures in random models where we tried to argue the importance of going beyond degree distribution: tinyurl.com/yxna36n7 , and (partial) k-trees had the desirables

random k-trees share the expected/desirable power law distribution in node degrees, like Barabasi-Albert, but B-A lacks higher-order statistics like clique/clustering distributions that k-trees also exhibit. And there are other higher-order distributions that k-trees have which match real-world distributions (like edge embeddedness and overlapping clusters) which other models have.

can you generate those diagrams from the random graph distributions which have been studied specifically for their degree distribution: random k-trees and Barabasi-Albert models, maybe also the small-world model of Watts-Strogatz?

@HarryGindi I don't know which one of is being more hard on people in #2... me saying that they present in a smug manner or you saying that they lack a skill in presenting :D

You are using the term 'induced cycle' inappropriately and it must absolutely be used correctly to be able to discuss these concepts. Also, please include citations for Ravindra, and for the later result that Meyniel graphs were proven strongly perfect.

without any structure in the graph paths or in the sets weights, essentially all paths woul have to be checked ... unless in a shortest path problem, where a path from s-t going through an intermediate u, it doesn't matter how s gets to u, just the value at u is important. But the unio nof all your sets along the way would be different for every s-to-u path, so essentially all paths would have to be considered.

I have not seen this problem studied before. Sets on vertices have been used in describing graph dimension or list-colouring or preference lists in stable matching problems, for example. In general, intersection graphs are graphs where each vertex is a set and an edge represents a non-empty intersection of the two vertices. Those sets are sometimes geometrical points, or intervals of real lines, or just discrete sets.

Hmmm... you are right ... induction would be saying that a property holds for everything on the 1,2,4,8,16 .... path. I guess one actually has to find a different set for this, rather than a successfor function. Answer now edited to reflect this.