GRAPH THEORY
UNDIRECTED GRAPHS
Definition 01:graph
A graph G is an ordered pair of elements, G = <> where V(G) is a non-empty finite set of elements, called vertices (singular is vertex) and E(G) is a set of unordered pairs of elements called edges and are denoted by [x,y], x,y Є V(G).
Definition 02:DEGREE OF VERTEX X
The degree of a vertex x in a graph G denoted by deg(x) is the number of edges incident to x where a loop is counted twice.
Definition 03:ISOLATED VERTEX
A vertex x is an isolated vertex if deg(x) = 0
Definition 04:SIMPLE GRAPH
Simple graph is a graph with no loops and no multiple edges.
Definition 05:ORDER AND SIZE
Let G be a graph, the order of G is │V(G)│ while the size of G is │E(G)│.
Definition 06:R-REGULAR
A graph G is said to be r-regular if deg(x) = r for all x Є V(G).
Definition 07:WALK
Let G be a graph, a walk of length K is a sequence [x1, x2, .. xk, xk+1], x1, x2, .. xk+1 Є V(G) such that [xi, xi+1] Є E(G) for all 1 ≤ i ≤ k.
Definition 08:CLOSED WALK
A walk is said to be closed if x1 = xk+1 and k > 0.
Definition 09:PATH
A walk is called a path if the terms of the sequence are distinct.
Definition 10:CYCLE
A walk is called a cycle, if it is closed, its edges are distinct and if [x1, x2, x3, … xk] are distinct. A cycle is denoted by Cn where n is the number of vertices.
Definition 11:DISTANCE
The distance between vertices u and v, denoted by d(u,v), is the length of the shortest path connecting u to v. If no paths between u and v exists, then d(u,v) is not defined.
Definition 12:CONNECTED GRAPH AND DISCONNECTED GRAPH
A graph G is connected if there is a path between x and y for all x,y Є V(G). A graph which is not connected is said to be disconnected.
Definition 13:DIAMETER
The diameter of a connected graph G denoted by d(G) is the maximum distance between its two vertices.
Definition 14:SUBGRAPH
Let G be a graph, we call H a subgraph of G if V(H) is a subset of V(G) and E(H) is a subset of E(G).
Definition 15:SPANNING SUBGRAPH
If H is a subgraph of G and V(H) = V(G) then H is a spanning subgraph of G.
Definition 16:PROPER SUBGRAPH
Let G and H be graphs. If H is a subgraph of G but H ≠ G, then H is a proper subgraph of G.
Definition 17:COMPONENT
A connected component of G (or simply component) is any maximal connected subgraph of G.
Definition 18:COMPLEMENT
Let G be a graph. The complement of G, denoted by Ğ is the simple graph with V(G) = V(Ğ) and for all [x,y] Є E(Ğ) iff [x,y] is not an element of E(G).
Definition 19:ISOMORPHISM
Let H and G be graphs. A mapping Ø : V(G) -> V(H) is called isomorphism if Ø is bijective and [x,y] Є E(G) iff [Ø(x), Ø(y)] Є E(H). We say that G is isomorphic to H if there exist an isomorphism Ø : V(G) -> V(H).
Definition 20:SELF-COMPLEMENTARY
A graph is called a self complementary if G ~ Ğ.
Definition 21:ACYCLIC
A graph which does not contain cycles is called acyclic.
Definition 22:TREE
A connected acyclic graph is called a tree.
Definition 23:END VERTEX / PENDANT / LEAF
A vertex x in a tree is called an end vertex / pendant vertex / leaf if degree x = 1.
A forest is a graph with the property
Definition 25:CUT VERTEX
A vertex x is called a cut vertex if the removal of x increases the number of components in G.
Definition 26:BRIDGE
A bridge is an edge whose removal increases the number of components of a graph.
Definition 27:BLOCK
A block is a graph with no cut vertex
Definition 28:COMPLETE GRAPH
A complete graph denoted by Kn where n is the order of Kn, is a simple graph such that [x,y] Є E(Kn) for all x,y Є V(Kn) and x ≠ y.
Definition 29:BIPARTITE GRAPH
A graph G is bipartite if V(G) can be partitioned into two subsets x and y such that each edge joins a vertex in x to a vertex in y. A bipartite graph with m vertices in x and n vertices in y is denoted by Bmn.
Definition 30:COMPLETE BIPARTITE GRAPH
A graph G is a complete bipartite if V(G) can be partitioned into two subsets x and y such that every vertex in x is joined in every vertex in y. It is denoted by Kmn.
Definition 31:PLANAR GRAPH
A graph G is called a planar graph if it is possible to draw G in the plane without edge crossing.
Definition 32:STAR
A star is a graph denoted by Sn if there are n-1 end vertices incident to a vertex x called the central vertex.
Definition 33:HAMILTONIAN GRAPH
A graph G is said to be Hamiltonian if it contained a spanning cycle.
Definition 34:EULERIAN GRAPH
A graph G is said to be Eulerian if it is a closed, spanning walk using each edge of G only-once / exactly-once.
Definition 35:CARTESIAN PRODUCT
Let G and H be two graphs. The Cartesian Product of G and H which is denoted by G x H is the graph with V(GxH) = V(G) x V(H) and ordered pairs (x,y) and (u,v) are adjacent if and only if x = u and [y,v] Є E(H) or y = v and [x,u] Є E(G).
Definition 36:SUM OF G AND H
Let G and H be two graphs with disjoint vertex sets. The sum of G and H denoted by G+H is the graph with V(G+H) = V(G) U V(H) and E(G+H) = E(G) U E(H) U { [x,y] such that x Є V(G), y Є V(H) }.
Definition 37:VERTEX GLUING
Let G and H be two graphs with disjoint vertex sets. A vertex gluing of G and H denoted by G*H is a union of a vertex x in V(G) and a vertex y in V(H) where E(G*H) = E(G) U E(H).
Definition 38:INDEPENDENT SET
Let G be a graph, a set S of V(G) is called an independent set if for all x,y Є S, [x,y] is not an element of E(G).
Definition 39:LABELLING F
A labelling f of a graph G is a one to one function f : V → Z+.
Definition 40:GRACEFULL LABELLING
Let G be a graph with m edges. A graceful labelling of G is a one to one mapping f : V(G) → { 0, 1, 2, 3, …m } such that the induced mapping f* : E(G) → { 1, 2, 3, …m } is defined by f* (Ui , Ui+1) = │f (Ui+1) – f (Ui)│is one to one function and onto function.
Definition 41:GRACEFUL
A graph which admits a graceful labelling is said to be graceful.
Definition 42:CROWN
A crown denoted by Crn is a cycle with a pendant edge attached at each vertex. (n denotes the order of the cycle)
Definition 43:FLOWERETTE
Let x and y be any two cycle vertices adjacent to a cycle vertex z of a crown which cycle Cn and v be the pendant vertex adjacent to z. A flowerette, denoted by Ftn is a graph obtained by deleting the pendant edge attached to z, joining the pendant vertex v to each x and y and then repeating the procedures using all the other pendant edges and vertices.
Definition 44:digraph
A digraph (or directed graph) D is a finite set V of objects called vertices together with a set A of ordered pairs of distinct vertices. The elements of A are called directed edges or arcs or
Definition 45ORIENTED GRAPH
If a digraph D has the property that for each pair u,v of distinct vertices of D, at most one of (u,v) and (v,u) is an arc of D, then D is an oriented graph.
Definition 46:ADJACENT TO AND ADJACENT FROM
If (u,v) Є A(D), then u is said to be adjacent to v and v is adjacent from u.
Definition 47:OUT DEGREE AND IN DEGREE
The number of vertices to which a vertex u is adjacent, is the out degree of v, and is denoted by od(v). On the other hand, the number of vertices from which a vertex u is adjacent, is the in degree of v, and is denoted by id(v) or;
Definition 48:SOURCE
A vertex v in V(D) is a source if:
od(v) > 1
Id(v) = 0
Definition 49:SINK
A vertex v in V(D) is a sink if:
od(v) = 0
Id(v) > 1
Definition 50:CARRIER
A vertex v in V(D) is a carrier if:
od(v) = Id(v) = 1
Definition 51:ISOLATED VERTEX
A vertex v in V(D) is an isolated vertex if:
od(v) = Id(v) = 0
Definition 52:SUBDIGRAPH
A digraph H is called a subdigraph of a digraph D if V(H) is a subset of V(D) and A(H) is a subset of A(D).
Definition 53:SYMMETRIC
A digraph D is symmetric if whenever {(u,v)} C A(D), then {(v,u)} C A(D) as well.
Definition 54:DIRECTED WALK
Let D be a digraph. A sequence w : u = u0, u1, .. uk = v of vertices of D such that u is adjacent to ui+1 for all i(1 <>(directed) u-v walk of length k in D. The number of occurrences of arcs on a walk is the length of the walk.
Definition 55:DIRECTED TRAILD AND DIRECTED PATH
A walk in which no arc is repeated is a (directed) trail; while a walk in which no vertex is repeated is a (directed) path.
Definition 56:UNDERLYING GRAPH
If a digraph D is an orientation of a graph G, then G is the underlying graph of D.
Definition 57:CONNECTED AND STRONG
A digraph D is connected (sometimes called weakly connected) if the underlying graph G is connected. A digraph D is strong (sometimes called strongly connected) if D contains both a u – v path of a v – u path for every pair, u,v of distinct vertices of D.
Definition 58:DIRECTED DISTANCE
Let u,v Є V(D). The directed distance or more simply, the distance d(u,v) from u to v is the length of the shortest u – v path in D. A u – v d(u,v) path of length is a u-v geodesic.
END.
UNDIRECTED GRAPH
Def 1. A graph G is an ordered pair of elements, G =
Def 2. Let G be a graph with V(G) and E(G). The order of G is the number │V(G)│ while the size of G is │E(G)│.
E(G) – edges
Multiple Edge
- an edge is a multiple edge if that is considered as more than one element of E(G).
- repetition of the edges in the same vertex
- initial and terminal point are the same
Def 3. The degree of a vertex x of a graph G denoted by the degree of x or deg(x) where x Є V(G) is equal to the number of edges containing x where a loop is counted twice.
Def 4. A graph G is k-regular if the degree of x is equal to K for all x Є V(G).
Def 5. Simple graph is a graph with no loops and multiple edges.
Def 6. Let G be a graph, a walk of length K is a sequence [x1, x2, x3, .. xk, xk+1] v(G) such that [xi, xi+1] Є E(G) for all 1 ≤ i ≤ k.
Def 7. A walk is said to be closed if x1 = xk+1 and k > 0.
Def 8. A walk is called a path if the term of the sequence are distinct.
Def 9. A walk is called a cycle if it is closed, its edges are distinct and x1, x2 .. xk are distinct.
Def 11.Let G be a graph, we called H a subgraph of G if V(H) is a subset of the V(G) and E(H) is a subset E (G).
Def 12. If H is a subgraph of G but H ≠ G, then H is a proper subgraph of G.
Def. 13. If H is a subgraph of G and V(H) = V(G) then H is a spanning subgraph of G.
Def 14. If H is a subgraph of G and H is not a proper subgraph of a subgraph of G having the vertex set V(H), we called H as induced subgraph of G.
Def 15. A connected component of G (or simply component) is any maximal connected subgraph of G.
Def 16. A graph is said to be r-regular if deg(x) = r for each vertex x in it.
Def 17. Let G be a graph. The complement of G1 denoted by G-bar is the simple graph with V(G) = V(G-bar) and for all [x,y] Є E(G-bar) iff [x,y] is not an element of E(G).
Def 18. Let H and G be graphs. A mapping Ø: V(G) -> V(H) is called isomorphism if it is bijective and [x,y] Є E(G) iff [Ø(x), Ø(y)] Є E(H). We say that G is isomorphic to H if there exist an isomorphism Ø : V(G) -> V(H).
Thm 1. Let Ø: V(G) -> V(H) be an isomorphism then the deg(x) = deg [Ø(x)] for each x Є V(G). That is, an isomorphism preserves degree.
Def 19. A graph is called a self complementary if G ~ G-bar.
Def 20. A graph which does not contain cycles is called acyclic.
Def 21. A connected acyclic graph is called a tree.
Def 22. A forest is a graph with the property that each of its components is a tree.
Def 23. A vertex x in a tree is called an end vertex/pendant/leaf if degree x = 1.
Thm 2. Let T be a tree of order n and size m. Then m = n – 1.
Def 24. The complete graph of order n, denoted by kn is the graph such that [x,y] Є E (kn) for all x,y Є V(kn).
Properties of kn
1. the degree is n-1
2. the size is (n2-n)/2
3. connected
4. n-1 regular
Def 25. A graph G is bapartite if V(G) can be partitioned into a subsets x and y such that each edge joins a vertex in x to a vertex in y. A barpartite graph with m vertices in x and n vertices in y is denoted by Bmn.
Def 26. Let G be the disjoint union of two complete graph Km and Kn. Then G-bar is called a complete bipartite graph and is denoted by Kmn.
Properties of Kmn
1. size = mn
2. order = m+n
3. connected
4. regular if m = n
Def 27. A graph G is called a planar graph if it is possible to draw G in the plane without edge crossing.
Def 28. A graph G is said to be Hamiltonian if it contain a spanning cycle.
Def 29. A graph G is said to be Eulerian if it is a closed spanning walk using each edge of G exactly once.
Def 30. A vertex x in graph G is called cut vertex if the removal of x increases the number of connected component of G.
Def 31. A bridge is an edge whose removal increases the number of components of a graph.
Def 32. The Cartesian product of G and H which is denoted by G x H is the graph with V(GxH) = V(G) x V(H) and ordered pairs (x,y) and [u,v] are adjacent if and only if x=u and [u,v] Є E(H) or y=v and [x,u] Є E(G).
Def 33. Let G and H be two graphs with disjoint vertex sets, the sum of G and H denoted by G + H is the graph with the sum V (G+H) = V(G) U V(H) and E(G+H) = E(G) U E(H) V {[x,y] such that x Є V(G), y Є V(H).
Def 34. Let G and H be a two graph with disjoint vertex sets, a vertex gluing of G and H denoted G * H is a union of vertex x Є V(G) and a vertex y Є (H) where the E (G*H) = E(G) U E(H).
Def 35. Distance of two vertices x,y denoted by d(x,y) is the length of any shortest path with end vertices x,y.
Def 36. The diameter of graph G denoted by d(G) = maximum {d(x,y) such that x,y Є v(G)}.
Def 37. Let G be a graph K > 0 be an integer, the Kth power of G denoted by Gk is the graph whose vertex is the vertex set of G and whose edges is [x,y] Є E(Gk) iff d(x,y) < k, x ≠ y, and x,y Є V(Gk).
Def 38. A labelling f of a graph G is a one to one function f: v -> Z+.
Def 39. Let G be a graph with m edges, a graceful labelling of G is one to one mapping f: v(G) -> {0,1,2,..,m} such that, the induced mapping f*: E(G) -> {1,..,m} is defined by f* (ui,ui+1) = │f(ui+1) -f(ui)│ is one to one function and onto function.
Def 40. A graph which admits a graceful labelling is said to be graceful.
Def 41. A star denoted by Sm+1 is a graph with m pendant vertices attached to a single vertex called a central vertex.
Def 42. A Crown denoted by Crn is a cycle with a pendant edge attached at each vertex.
Def 43. Let x and y be any two cycle vertices adjacent to a cycle vertex z of a crown with cycle Cn and V be the pendant vertex adjacent to z. A flowerette denoted by Ftn is a graph obtained by deleting the pendant edge attached to z, joining the pendant vertex V to each of x and y and then repeating the procedures using all the other pendant edges and vertices.
Def 44. Let w be a bud vertex a and z be a petal vertex which are both attached to each of the bud vertices x and y of Fth. A k-regular bipartide graph denoted by Bn can be obtained by joining every vertex w to every vertex z and deleting all bud edges of Fth.
Def 45. The bandwith of f for a graph G denoted by B (G,f) is defined by B (G,f) = max {│f(x) -f(y)│} for all [x,y] E(G).
Def 46. The Bandwith of G, denoted by B(G) is defined by B(G) = min {B (G,f): f is a labelling of G}
DIRECTED GRAPH
Def 1. A di-graph or directed graph is a pair D =
Def 2
Def 3. A vertex x in a digraph D is
3.1 a source if the od(x)>0 and id (x)=0
3.2 a sink if the id(x)>0 and od(x)=0
3.3 a carrier if the id(x)=od(x)=1
3.4 an isolated v it id(x)=od(x)=0
Def 4. Let D be a digraph with vertices x1,x2,..xn. the adjacency matrix of a digraph D is the nxn matrix where aij={1 if (xi,xj) Є A(D) ; 0 if (xi,xj) is not an element of A(D)}
Def 5
Def 6 A walk in a given sequence where [x1,x2,.. xk,xk+1] is said to be closed if x1 = xk+1 and k > 0 are distinct. It is called a path if x1.., xk. A closed walk is called a circuit if k>0 and x1..xk are distinct.
Def 7
Def 8
Def 9
Def 10. A tournament is a digraph which does not contain loop and such that there is one arc in every pair of vertices.
Def 11
Def 12
Def 13
Def 14. Let D be a digraph with m arcs and let f be a mapping from the set of vertices f: V(D) -> {0,1,2,..,m} be a 1-1 mapping. If the difference {f(x) - f(y) as (x,y) ranges over all arc of D are distinct modulo m+1 and none of them is ≡ to 0 mod m+1 then f is graceful labelling of D. D is graceful if it admits the graceful labelling.
Def 15. Let D be a digraph with m arcs. A 1-1 mapping f:V(D) -> {0,1,2,…m} is called residually graceful labeling of D if the difference f(x) – f(y) as (x,y) ranges over all arcs of D, form a complete residue system mod m, then f is a residually graceful labeling of D. A digraph which admits a residually graceful labeling is graceful.
Theorems on Gracefulness of Graphs:
· If each vertex of G is of even degree and the number of edges is congruent to either 1 or 2 mod 4, then G is not graceful.
· If G is graceful graph with no edges, then G * P2 is not graceful.
· If G is a graceful graph with m edges, then G * P3 is graceful.
Theorems on Nongracefulness of Graphs:
· If one of n,m is congruent to 0 mod 4 and the other is congruent to 2 mod 4, then Cm + Cn is not graceful.
other version..
UNDIRECTED GRAPH
Definition 1: A graph G is an ordered pair of elements, G = where V(G) is a non-empty finite set of elements, called vertices and E(G) is a set of unordered pairs of elements V(G) called edges and are denoted by [x,y], x,y ε V(G).]
Definition 2: Let G be a graph with V(G) and E(G). The order of G is the number of elements of│V (G)│, while the size of G is the number of elements of │E (G)│.
Definition 3: The degree of a vertex x of a graph G denoted by the deg(x) where x Є V (G) is equal to the number of edges containing x where a loop is counted twice.
Definition 4: A graph G is k-regular if the deg(x) = k for all x ε V (G).
Definition 5: A simple graph is a graph with no loop nor multiple edges.
Definition 6: Let G be a graph, a walk of length k is a sequence [x1, x2,…xk, xk+1] of vertices in G such that [xi, xi+1] Є E(G) for all 1<>
Definition 7: A walk is said to be closed if x1= xk+1 and k> 0.
Definition 8: A walk is called a path if the terms of the sequence are distinct.
Definition 9: A walk is called a cycle if it is closed, its edges are distinct and if [x1, x2,…,xk] are distinct.
Definition 10: A graph G is said to be connected if for all x,y Є V(G) there exist a walk/path joining x and y. A graph which is not connected is said to be disconnected.
Definition 11: Let G be a graph, we call H a subgraph of G if, the V(H) is a subset of the V(G) and the E(H) is a subset of the E(G). Denotation: V(H) C V(G)
Definition 12: If H is a subgraph of G, but H ≠ G then H is a proper subgraph of G.
Definition 13: If H is a subgraph of G and V(H) = V(G) then the vertex set of H is equal to the vertex set of G, then H is the spanning subgraph of G.
Definition 14: If H is a subgraph of G, and H is not a proper subgraph of a sub graph of G having the V(H), we called H an induced subgraph of G.
Definition 15: A connected component of G (or simply component) is any maximal connected subgraph of G.
Definition 16: A graph is said to be r-regular if deg (x) = r for each vertex x in it.
Definition 17: Let G be a graph. The complement of G, denoted by G is the simple graph with V(G) = V(G) and for all [x,y] Є E(G) iff [x,y] is not an element of E(G).
Definition 18: Let H and G be graphs. A mapping Ф: V(G) →V(H) is called isomorphism if Ф is objective and [x,y] Є E(G) iff [Ф (x), Ф (y)] Є E(H). We say that G is isomorphic to H if Э an isomorphism Ф : V(G) →V(H).
Theorem 1: Let Ф: V(G) →V(H) be an isomorphism, then the degree of x is equal to the degree of (Ф (x)) for each x element of V(G). That is, an isomorphism preserves degree. Definition 19: A graph is called a self-complementary if G ~ G.
Definition 20: A graph which does not contain cycles is called acyclic.
Definition 21: A connected acyclic graph is called a tree.
Definition 22: A forest is a graph with the property that each of its component is a tree.
Definition 23: A vertex x in a tree is called an end vertex/pendant vertex/leaf if deg x = 1.
Theorem 2: Let T be a tree of order n and size m, then m = n-1.
Definition 24: The complete graph of order n denoted by Kn is the graph such that [x,y] Є E(Kn) for all x, y Є V(Kn).
Definition 25: A graph G is bipartite if V(G) can be partitioned into 2 subsets x and y such that each edge joins a vertex in x to a vertex in y. A bipartite graph with m vertices in x and n vertices in y is denoted by Bmn.
Definition 26: Le G be the disjoint union of two complete graphs Km and Kn. Then G is called a complete bipartite graph and is denoted by Kmn.
Definition 27: A graph G is called a planar graph if it is possible to draw G in the plane without edge-crossings.
Definition 28: A graph G is said to be Hamiltonian if it contains a spanning cycle.
Definition 29: A graph is said to be Eulerian if it is a closed spanning walk using each edge of G exactly/only once.
Definition 30: A vertex x in a graph G is called a cut vertex if the removal of x increases the number of connected components.
Definition 31: A bridge is an edge whose removal increases the number of components of a graph.
Definition 32: Let G and H be two graphs. The Cartesian product of G and H which is denoted by G x H is the graph with V ( G x H ) = V(G) x V(H) and ordered pairs (x,y) and (u,v) are adjacent if and only if x = u and [ y,v ] Є E(H) or y = v and [ x,u ] Є E(G).
Definition 33: Let G and H be two graphs with disjoint vertex sets. The sum of G and H denoted by (G+H), is the graph with V(G+H) = V(G) U V(H) and E (G+H) = E(G) U E(H) U [x,y] such that x Є V(G), y Є V(H).
Definition 34: Let G and H be two graphs with disjoint vertex sets. A vertex gluing of G and H denoted by G*H is a union of vertex x Є V(G) and y Є V(H) where E(G*H) = E(G) U E(H).
Definition 35: The distance of 2 vertices x,y denoted by d(x,y) is the length of any shortest path with end vertices x,y.
Definition 36: The diameter of a graph G denoted by d(G) = maximum d(x,y) such that x,y Є V(G) . ` Definition 37: Let G be a graph and k>0 be an integer. The kth power of G, denoted by Gk is the graph whose vertex set is equal to V(G) and whose edges is the set [ x, y ] Є E (Gk) iff d(x,y) <>
Definition 38: A labeling f of a graph G is a function f: V→ Z+ which is 1-1.
Definition 39: Let G be a graph with m edges. A graceful labeling of G is a 1-1 mapping f: V(G) → { 0,1,2,3,…m } such that the induced mapping f*: E (G) → { 1,2,3,…m } is defined by f* (Ui , Ui+1) = │f (Ui+1) – f (Ui)│is 1-1 and onto.
Definition 40: A graph which admits a graceful labeling is said to be graceful.
Definition 41: A star, denoted by S m+1 is a graph with m pendant vertices attached to a single vertex called a central vertex.
Definition 42: A crown, denoted by Crn is a cycle with a pendant edge attached at each vertex. (n denotes the order of the crown)
Definition 43: Let x and y be any two cycle vertices adjacent to a cycle vertex z of a crown which cycle Cn and v be the pendant vertex adjacent to z. A flowerette, denoted by Ftn is a graph obtained by deleting the pendant edge attached to z, joining the pendant vertex v to each x and y and then repeating the procedures using all the other pendant edges and vertices.
Definition 44: Let w be a bud vertex and z be a petal vertex which are both attached to each of the bud vertices x and y of Ftn. A three-regular bipartite graph denoted by Bn can be obtained by joining every vertex w to vertex z and then deleting all the bud edges of Ftn.
Definition 45: The bandwidth of f for a graph, denoted by B( G,f) is defined by B( G,f ) = max {│f(x) – f(y)│} for all [ x,y ] Є E(G).
Definition 46: The bandwidth of G, denoted by B(G) is defined by B(G)=min {B(G,f); f is a labeling of G}.
DIRECTED GRAPH
Definition 1: A digraph (directed graph) is an ordered pair of D= where V(D) is a non-empty finite set and A(D) is a relation on V(D). The elements of V(D) are called vertices and the elements of A(D) are called arcs. The order of D is the number │V(D)│ and the size of D is the number │A(D)│.
Definition 2: Let D be a graph. If (x,y) Є A(D) then we say that x is adjacent to y. The out-degree of a vertex x denoted by od(x) is the number of vertices y such that (x,y) Є A(D) and the in-degree denoted by id(x) is the number of vertices y such that (y,x) Є A(D).
Definition 3: A V(x) in a digraph is called 3.1 A source if the out-degree of x is greater than zero and in-degree of x is equal to zero. 3.2 A sink if out-degree of x is equal to zero and the in-degree of x is greater than zero. 3.3 A carrier if in-degree of x is equal to out-degree of x which is equal to 1. 3.4 An isolated vertex if in-degree of x is equal to out-degree of x which is equal to zero.
Definition 4: Let D be a digraph with vertices (x1, x2,…xn). The adjacency matrix of a digraph D is the n x n where aij = { 1 if (xi, xj) Є A(D); 0 if (xi, xj) Є A(D).
Definition 5: Let D be a digraph. A walk of length k in D is a sequence of vertices [x1, x2,…xk xk+1] such that (xi, xi+1) is an element of A(D) where i=1,2,3,…k
Definition 6: A walk in a given sequence [x1, x2,…xk,,xk+1] and k>0. A walk is closed if x1= xk+1 and k>0. Is called a path if x1, x2,…,xk+1 are distinct. A closed walk is called a circuit if k>0 and x1, x2,…xk are distinct.
Definition 7: Two digraphs D and H are said to be isomorphic if there exist a bijective mapping; Ф:V(D)→V(H) such that (x,y)ЄA(D) if and only if x,y Є V(D) such a mapping is called an isomorphism.
Definition 8: Let D be a digraph. The converse of D denoted by Dc is the digraph with the following: Dc = where A(Dc)= {(x,y) such that (y,x) ЄA(D), x,y ЄV(D)}
Definition 9: A digraph D is said to be self-converse if D is isomorphic to Dc.
Definition 10: A tournament is a digraph which does not contain loops and such that there is exactly one arc between every pair of vertices.
Definition 11: The score of a vertex in the tournament denoted by S(x) is defined as S(x)=od(x).
Definition 12: The score vector of a tournament id the non-decreasing sequence of the scores of the vertices. The score vector [S1, S2,…Sn,] where n is the order of the tournament.
Definition 13: Let T be a tournament and x,y,z be elements of vertex set [V(T) of T. The set {x,y,z} is called a transitive triple if those elements do not form a circuit.
Definition 14: Let D be a digraph with m arcs and let f:V(D)→{0,1,2,…m) be a 1-1 mapping. If the difference f(x) – f(y) as (x,y) ranges over all arcs of D, are the distinct mod m + 1 and none of them is congruent to 0 mod m + 1, then f is a graceful labeling of D. D is graceful if it admits a graceful labeling.
Definition 15: Let D be a digraph with m arcs. A 1-1 mapping f:V(D)→{0,1,2,…m} is called residually graceful labeling of D if the difference f(x) – f(y) as (x,y) ranges over all arcs of D, form a complete residue system mod m, then f is a residually graceful labeling of D. A digraph which admits a residually graceful labeling is graceful.
Theorems on Gracefulness of Graphs:
- If each vertex of G is of even degree and the number of edges is congruent to either 1 or 2 mod 4, then G is not graceful.
- If G is graceful graph with no edges, then G * P2 is not graceful.
- If G is a graceful graph with m edges, then G * P3 is graceful.
Theorems on Nongracefulness of Graphs:
If one of n,m is congruent to 0 mod 4 and the other is congruent to 2 mod 4, then Cm + Cn is not graceful.
(some characters are missing due to posting problem)
posted by JM RAM at 11:41 PM
3 comments
