The Gateway to Computer Science Excellence
+3 votes
For which values of m and n is Km,n regular?
in Graph Theory by Boss (16.2k points) | 611 views

sourav km,n(complete graph) is always regular for m=n  

Km,n is complete bipartite graph.

It is regular too

As we can say  complete graph is a subset of regular graph
its asking about complete bipartite graph.what should be the value of m,n to make complete bipartite graph  a regular graph.

according to me it should be m=n=n/2....just want to verify
complete bipartite graph $\subset$ complete graph $\subset$ regular graph

So, put any value in m,n
A regular graph is a graph in which all the vertices have same degree....yes obviously complete graph is (n-1)regular graph.

here in the question it is given Km,n  i.e it is a complete bipartite graph but it is not true that for ny value of m,n it will be a regular bipartite graph...let us take K2,3 ..i.e m=2 and n=3 now it will be degree having 3,3,2,2,2.

If we take k 2,2 (m=n)now the degree will be 2,2,2,2

I think bipartite graph like something different to think

yes $K_{2}$ is isomorphic to $K_{2,2}$

but is $K_{3}$ is isomorphic to $K_{3,3}$ ? No

$K_{3}$ is planer where $K_{3,3}$  is non planer

Similarly $K_{2,3}$ has 2 partition in the graph and each partition has regular by itself
not as a whole it is not regular ...!!!!

if you are asked to write the degree sequence of K2,3 then it will be 3,3,3,2,2

but has to be n,n,n,n,n for Kn,m where n=m;
Is complete bipartite graph is complete graph?

What will be ur answer? definitely No

but it is complete as a bipartite graph.

Similarly as it is regular bipartite graph , as a whole No bipartite graph could be regular. .

Do, u think $K_{3,3}$ is a regular graph? No .

Yes ,a complete bipartite graph can be regular graph K m,n provided m=n

reference (exmpl 3)

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,398 answers
105,457 users