[Graph theory] How should this be called?

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

  1. (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)


    Dear newsgroup reader,

    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
    #1
    1. Advertisements

  2. 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
    #2
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.