graph theory: quick question(s)

JaeSun

what's the difference between a subgraph and an induced subgraph?

looking here:

http://mathworld.wolfram.com/InducedSubgraph.html

how is the figure K8 ? isn't that K10 ??

also, what is a spanning subgraph?

shmoe

That's K10.

If there is an edge in a graph between two vertices in an induced subgraph, then that edge must be in the induced subgraph as well. If you start with a graph and delete only vertices (as well as any edges that share an end with a deleted vertex), you get an induced subgraph. You can also think of this as the maximal subgraph (in the sense of it's edges) containing a given vertex set. A plain old subgraph has no such restrictions on it's edges. If you look at that K10 example, the subgraph consisting of the vertices {1, 2, 3, 5, 7, 10} and NO edges is a subgraph, but not an induced subgraph.

A spanning subgraph contains all the vertices of your original graph.

Something for you to think about-what can you say about an induced subgraph that is a spanning subgraph as well?

JaeSun

oh ok, so a subgraph can contain no edges .... but that is not induced...in order to be induced, it has to be of the original vertex set with edges (that belonged to the edge set of the original graph) ?

its not a complete graph?

JaeSun

another question.

what is the independent number/set ?

http://mathworld.wolfram.com/IndependentSet.html

looking at that, and a problem from my homework which the answer is 4:

http://www.nevada.edu/%7Ebaragar/cou...1ex2sample.pdf

problem # 1b finding the independence number

is the independence set = {b, d, g, f}

??

and that is how the answer is 4?

shmoe

The only spanning induced subgraph of a graph G is G itself.


Take a subset of vertices of a graph. Look at the corresponding induced subgraph. If it contains no edges, your vertices are independant. If it contains any edges, they are not independant.

To show the independant number of the graph in your homework is 4 you can do two things:

Find an independant set of four vertices, this should be easy.

Next show that every set containing 5 vertices must have an edge between 2 of the vertices. For a hint, can the vertex c be in an independant set with 5 vertices?

philosophking

"in order to be induced, it has to be of the original vertex set with edges (that belonged to the edge set of the original graph)?"

I don't think this is right. You don't need all the vertices from the original graph, just if you take some subest of vertices, you have to include all of the edges that are incident to the nodes.