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:
ngak!
definisyons daw to,.
\sbi ni jay..
kaya pla nadugo ilong ko,..
wakokoko..\
ng blo blog ka pla?
ceryoso??
wushuuu!
WHOA!!! graph theory ba itu!!! dinala aku d2 ng aking pananaliksik d2.... at poof! coco-crunch.... nwei, *serious mode* bakit d aku makahanap ng kahit anong reference sa residually graceful labeling, properly graceful, at graceful labeling???? mukhang sinaung kaaklatan ata ginamit na reference ng prof namin...at ung nga itu c aku nagcocoment d2 dhil may tga-earth pa plang may nakaalam sa residually graceful labeling..
hmmm.... comsci kba??? electronics??? anu pu course nyo?? aku pu math for teacher..at hindi ku pa rin lubos maisip bkit nagkaron ng graph theory sa curriculum namen e ni d naman namin un ituturo sa secondary or tertiary level....
thanks for this dedinitions.. it helps a lot
Post a Comment
<< Home