i want to know the basics of longest cycle in a grpah.?

Question

someone plzz help me with these things abt longest cycles

i want to know the definition.
if possible its algo and complexity.
and does it have an approximation??

and its applications :)

Answer 1

The Basics


1.2 The degree of a vertex



Concepts
Regular: if all the vertices of G have the same degree k, then G is k-regular, or regular

Cubic: a 3-regular graph is called cubic









2-regular (C4)

3-regular (cubic, Q3)







Notations
d (G): minimum degree of graph G

D(G): maximum degree of graph G

d(G): average degree of graph G

dG(v): degree of vertex v in graph G

NG(v):neighbors of vertex v in graph G





1.3 Paths and cycles



Concepts
Girth: the minimum length of a cycle in a graph G

Circumference: the maximum length of a cycle in G

Chord: an edge that joins two vertices of a cycle but is not itself an edge of the cycle

Induced cycle: a cycle in G forming an induced subgraph, is one that has no chords. In another word, an induced cycle is a cycle without any chord.

Diameter: the greatest distance (length of shortest path) between any two vertices in G



Circumference (G) = 8

Chord (x, y)

xaph G

yaph G

Girth (G) = 4















Two induced cycles, C4, C6

Diameter (G) = 6



















Notations
g(G): girth of graph G

diam(G): diameter of graph G

xPy: path P from x to y



Proposition 1.3.1.Every graph G contains a path of length d(G) and a cycle of length at least d (G) +1, provided that d (G) ³ 2.

Proof.

1) G contains a path of length at least d (G)

Let v0, É,vk be a longest path in G. Then all the neighbors of vk lie on this path. This can be proved by contradiction. Assume there is a neighbor of vk does not lie on this path, say it is vj. Then we can add vj to path v0, É, vk to get a longer path v0, É, vk, vj, since (vk, vj) ë E(G). Thus, length(v0, É, vk) = k ³ d(vk) ³ d (G).

v0

vi

vk

vj











2) G contains a cycle of length at least d(G) + 1

Let i < k be the minimal on path v0, É, vk with (vi, vk) ë E(G). Then vi, É, vk, vi is a cycle of length at least d (G) +1, since all neighbors of vk are on the cycle.



Proposition 1.3.2.Every graph G containing a cycle satisfies g(G) ² 2 diam(G) + 1.

Proof. Prove by contradiction.

Assume g(G) ³ 2 diam(G) + 2, and let C be a shortest cycle in G. Then C must has two vertices (say x, y) whose distance in C is at least diam(G)+1.In G, x and y must have a shorter distance since the greatest distance between any two vertices is diam(G). Thus, there must be another shortest path P between x and y. Combining P with the shorter of the two x-y paths in C, we form a shorter cycle than C. Contradiction.

x

y

C

P

length(xPy)= distance(x, y) <= diam(G)

















1.4 Connectivity



Concepts
Connected: anon-empty graph G is called connected if any two of its vertices are linked by a path in G

Component: a maximal connected subgraph of graph G is called a component of G

Separate: X ê V é E, separates G if G- X is disconnected

k-connected: G is called k-connected if |G|> k and G - X is connected for every set X ê V with |X| < k. In other words, no two vertices of G are separated by fewer than k other vertices.

Connectivity: the greatest integer k such that G is k-connected

k-edge-connected: G is called k-edge-connected if |G| > 1 and G - F is connected for every set F ê E of fewer than k edges (|F| < k).

Edge-connectivity: the greatest integer k such that G is k-edge-connected









1-connected

2-edge-connected

2-connected

2-edge-connected







Notations
k(G): connectivity of G

l(G): edge connectivity of G

G

H













d (H) = 4

Connectivity (H) = 2

Edge connectivity (H) = 4

4-regular, d(G) = 4

Connectivity (G) = 4

Edge connectivity (G) = 4











Proposition 1.4.2. If G is non-trivial then k(G) ² l(G) ² d (G).

Proof.

1) l(G) ² d(G): all edges incident to a fixed vertex separate G.

2) k(G) ² l(G): Let F be any minimal subset of E such that G - F is disconnected.

Case 1. G has a vertex v that is not incident with an edge in F.

Let C be the component of G Ð F containing v. Then the vertices of C that are incident with an edge in F separate v from GÐ C. Since no edge in F has both endpoints in C (due to F is minimal), there are at most |F| such vertices, that is, k(G) ² |F|.

F

G

v

C

G Ð C

v is not incident with any edge in F



















Case 2. Every vertex in G is incident with an edge in F.

F

G

C

G Ð C

Every vertex is incident with an edge in F

Let v be any vertex, and let C be the component of G Ð F containing v. Then the neighbors w of v with (v, w) ì F lie in C and are incident with distinct edges in F, giving dG(v) ² |F|. As NG(v) separates v from all the other vertices in G, this yields k(G) ² |F|, unless there are no other vertices, i.e. unless {v} é NG(v) = V. But v was an arbitrary vertex. So we may assume G is a complete graph if k(G) = l(G) = |G|- 1.



















1.6 Bipartite graphs



Concepts
r-partite: a graph G=(V, E) is called r-partite if V admits a partition into r classes such that every edge has its ends in different classes. That is, vertices in the same partition class must not be adjacent.

Bipartite: 2-partite

Complete r-partite: an r-partite graph in which every two vertices from different partition classes are adjacent is called complete

Odd cycle: a cycle of odd length



Notations
Kn1,É,nr: complete r-partite graph

Ksr: complete r-partite graph in which every partition class contains exactly s vertices

3-partite

Complete 3-partite

K2,2,2 = K23



















Proposition 1.6.1. A graph is bipartite if and only if it contains no odd cycles.

Proof.

Assume G is connected (clearly a graph is bipartite if all its components are bipartite or trivial), and contains no odd cycles. Let T be a spanning tree in G, and a root r ë T. For each v ë V, the unique path from r to v on T (rTv) has either odd or even length. This defines a bipartition of V. For each edge e = (x, y) ë E(G),

Case 1. If e ë T, with x
Case 2. If e ì T, then Ce = xTy + e is a cycle. Since Ce is even, x and y lie in different classes.

y

x

Case 1

y

x

odd cycle

Case 2

y

x

even cycle