# [Graph theory] How should this be called?

Discussion in 'Math Research' started by Hiu Chung Law, Aug 29, 2003.

1. ### Hiu Chung LawGuest

(This question has also been posted in graphnet. However, since I do not
get any response thus far, I would like to seek the suggestion of
readers in this group as well)

Please forgive me if this question sounds trivial to you. I have done some
google and mathworld search on my question but I cannot find the answer.

Given any graph G, its clique number is defined as the size of the largest
clique in the graph. There is a theorem by Matula stating that in a class
of random graph, the clique number lies in a "short" interval for almost
every graph.

My question is: what happens if we replace "clique" by "regular graph"?
How should the quantity

max_r ( G has a r-regular graph as a subgraph )

be called? Is there any known result on this property for random
graphs?

Thank you!

Hiu Chung Law, Aug 29, 2003

2. ### Felix GoldbergGuest

A spanning r-regular graph is called an r-factor. So maybe your
quantity could be called an "r-subfactor"?

HTH,
Felix.

Felix Goldberg, Aug 30, 2003