Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I think in the graph theory operations such as decomposition into cycles, union, intersection, difference, subdivision can be done.

  • If I am given a planar graph (for e.g. see figure), then can the above operation do same as irrespective from the type of the graph? That my question is what ever common operation like above can be done with any type of graph?

  • Can anyone give mathematical notations for the above operations, for e.g. if I am given below graph, then how would be decomposition into shortest cycle, union of adjoining cycle, intersection, and difference can be represented?

enter image description here

share|improve this question
1  
You may want to explain what you are asking here, because right now the question is too vague. –  TMM Mar 28 '13 at 19:25

1 Answer 1

up vote 1 down vote accepted

Unions, intersections, and differences

Graph unions are probably what you'd guess they are. If $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are two graphs, then $$G_1 \cup G_2=(V_1 \cup V_2,E_1 \cup E_2).$$

I've never encountered graph intersections nor graph differences, but MathWorld (intersection; difference) defines them as $$G_1 \cap G_2=(V,E_1 \cap E_2)$$ and $$G_1 \setminus G_2=(V,E_1 \setminus E_2),$$ respectively, where the two graphs are assumed to have the same vertex set $V$.

In many cases in graph theory, it's easiest not to have fixed definitions because often we will need to use a slightly modified definition. Instead authors tend to give the relevant definitions when needed. I suspect the same holds true for $\cup$, $\cap$ and $\setminus$.

There's nothing to stop you from performing the operations $\cup$, $\cap$ and $\setminus$ on arbitrary pairs of graphs.

Decomposition into cycles

Decomposing a graph $G$ into cycles means to find an edge-disjoint family of cycles whose union (as defined above) is $G$. I don't believe there's any particular notation for this, typically $\{C_1,C_2,\ldots,C_k\}$ or something similar would suffice.

Since vertices in cycles have degree $2$, and the cycles in any decomposition are edge-disjoint, we must have:

Lemma: If $G$ admits a decomposition into cycles, then every vertex in $G$ has even degree.

The graph you drew in your picture, therefore, cannot be decomposed into cycles. Additionally, if $G$ is not the empty graph, then $G$ cannot have any isolated vertices.

If you don't want the edge-disjoint property, then you're talking about a graph covering (rather than a decomposition).

Planarity

One example of a non-planar graph is the $5$-vertex complete graph $K_5$. If $G_1$ is formed from $K_5$ by deleting an edge $e$, and $G_2$ is the graph formed from $K_5$ by deleting the edges other than $e$, then $G_1$ and $G_2$ are planar graphs, and $G_1 \cup G_2$ is $K_5$, and thus is non-planar. So, you can perform the operation $\cup$ on any two graphs, but it may take you outside of the family of planar graphs.

The intersection of two planar graphs will, however, be planar (since $G_1 \cap G_2$ is a subgraph of $G_1$). Similarly, the difference of two planar graphs will also be planar.

Subdivision

When we subdivide an edge $uv$, we (a) delete it (b) add a new vertex $w$ and (c) add the edges $uw$ and $wv$. We can do this many times, to obtain some graph that's called a subdivision of the original graph (ref.).

Again, I don't believe there's any common notation for this, aside from writing "subdivide the edge $e$" or similar.

Subdivision preserves the planarity of a graph, which is a fundamental part of Wagner's classification of planar graphs (known as Wagner's Theorem; see also Kuratowski's Theorem).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.