Definition 1.1
A graph G consists of a finite non-empty set V =
V(G) of p points (vertices) together with a prescribed set E = E(G) of q
unordered pairs of distinct points of V. Each pair χ = { a, b } of points in E
is a line (edge) of G and χ is said to join a and b. We write χ = ab and say
that a and b are adjacent points. Point ‘a’ and line ‘χ’ are incident with each
other, as are b and χ. If two distinct lines x and y are incident with a common
point, then they are adjacent lines. A graph with p points and q lines is
called a (p, q) graph.
Definition 1.2
The line joining a point to itself is called a
loop.
Definition 1.3
If
more than one line joining two vertices are allowed, the resulting object is
called a multigraph.
Definition 1.4
Lines joining the same points are called multiple lines.
Definition 1.5
A graph in which any two distinct points are
adjacent is called a complete graph.
The
complete graph with p points is denoted by Kp.
Definition
1.6
A graph whose edge set is empty is called a null graph or a
totally disconnected
graph.
Definition 1.7
A
graph G with p points is said to be a labeled graph, if all the p points of the
graph G are distinguished from one another by names such as v1, v2,
…, vp.
Definition 1.8
Two
graphs G and H are isomorphic if there exists a one-to-one correspondence
between their point sets which preserves adjacency.
Definition 1.9
A
sub graph of a graph G is a graph having all its points and lines in G. If G 1
is a sub graph of G, then G
is sub graph of G 1 .
Definition 1.10
A
walk of a graph G is an alternating sequence of points and lines v0, x1,
v1, x2, …, vn-1, xn, vn beginning and ending with points such that
each line xi is incident with vi-1 and vi .
We
say that the walk joints v0 and vn and it is called a vo-vn
walk. v0 is called the initial point and vn is called the
terminal point of the walk. The above walk is also denoted by v0, v1, …, vn the lines of the walk being self evident n,
the number of lines in the walk, is called the length of this walk.
A single point is considered as a walk of length
0.
Definition 1.11
A
vo-vn walk is called closed if vo = vn
Definition 1.12
A
walk is called a trail if all its lines are distinct.
Definition 1.13
A
walk is called a path if all its points are distinct.
Definition 1.14
A
closed walk v0, v1, v2 , …, vn = v0 in
which n ≥ 3 and v0, v1, …, vn-1 are distinct is called a cycle of length n.
The
graph consisting of a cycle of length n is denoted by Cn.
Definition 1.15
A
graph is connected if every pair of points are joined by a path.
Definition 1.16
A graph which is not connected is said to be
disconnected.
Definition 1.17
A maximal connected subgraph of a graph G is
called a connected component or simply a component of G.
Definition 1.18
The degree of a point vi in a graph G, denoted as di or deg vi, is the number of lines
incident with vi .
Definition 1.19
A graph G is said to be a regular graph if every
vertex is of same degree.
If every vertex of G is of degree n then G is said
to be a n – regular graph.
Definition 1.20
A bigraph (or bipartite graph ) G is a graph whose
point set V can be partitioned into two subsets V1 and V2
such that every line of G joints V1 with V2.
If G contains every line joining V1 and V2, then G is a
complete bigraph. If V1 and V2 have m and n points, we write G = Km,n = K (m, n ). A
star is a complete bigraph k1,n . Clearly Km,n has mn
lines.
Definition 1.21
A graph G is said to be acyclic if it has no
cycles.
Definition 1.22
A connected acyclic graph is called a tree.
Definition 1.23
A cutpoint of a graph G is a point whose removal
increases the number of components.
Definition 1.24
The connectivity K = K( G ) of a graph G is the minimum number of points
whose removal results in a disconnected or trivial graph. Thus the connectivity
of a disconnected graph is 0, while the connectivity of a connected graph with
a cutpoint is 1. The complete graph Kp cannot be disconnected by
removing any number of points, but the trivial graph results after removing p –
1 points; therefore, K( Kp ) = p -1, sometimes K is called the point
connectivity.
Definition 1.25
The line connectivity λ = λ ( G ) of graph G is the minimum number
of lines whose removal results in a disconnected or trivial graph. Thus λ (K1
) = 0 and the line connectivity of a disconnected graph is 0, while that of a
connected graph with a bridge is 1.
Definition 1.26
A set of points in G is independent if no two of
them are adjacent. The largest number of points in such a set is called the
point independence number of G and is denoted by β0 ( G ) or β0 . An
independent set of lines of G has no two of its lines are adjacent and the
maximum cardinality of such a set is the line independence number β1 (G)
or β1 .
Definition 1.27
A coloring of a graph is an assignment of colors to
its points so that no two adjacent points have the same color. The set of
points with any one color is independent and is called a color class. An n – coloring of a graph G uses n – colors;
it there by partitions V into n color classes. The chromatic number χ( G ) is
defined as the minimum n for which G has an n – coloring.
Definition 1.28
A k – edge
coloring α : EG → [ 1, k ] of a graph G is an assignment of k colors to its edges. We
write Gα to indicate that G has the edge coloring α .
A vertex v Є G
and a color i Є [ 1, k ] are incident with
each other, if α (vu) = i for some vu Є EG . If v Є
G is not incident with a color i, then i is
available for v.
The coloring
α is proper, if no two adjacent
edges obtain the same color: α (e1 )
≠ α (e2 ) for adjacent e1 and e2.
The edge chromatic number χ’(G) of G is defined as χ’ ( G ) = min { k | there exists a proper k – edge coloring of G
}. Definition 1.29
A complete p – partite graph G consists of p
discrete and disjoint induced subgraphs G1,G2,…..,Gp ⊆G, where
uv Є EG
if and only if u and v belong to different parts, Gi and Gj with i ≠ j . Note that a complete p –
partite graph is completely determined by its discrete parts Gi, i Є [ 1, p ].
Definition 1.30
A graph is a planar if it can be embedded in the
plane.
Embedding a graph in the plane is equivalent to
embedding it on the sphere.
Definition 1.31
A planar graph that is embedded in the plane is
called a plane graph.
Fig : 1 A planar and plane graph
Figure 1 (a) is a planar graph, though as drawn it
is not plane. The illustration in (b) is its plane representation.
Definition 1.32
Given a plane graph G, a region of G is a maximal
portion of the plane for which any two points may be joined by a curve A such
that each point of A neither corresponds to a vertex of G nor lies on any curve
corresponding to an edge of G.
The regions of G can be thought of as the disjoint
portions of the plane remaining after all the edges and vertices have been
removed.
Definition 1.33
The boundary of a region R of a plane graph G
consists of all points x corresponding to vertices and edges of G having the
property that x can be joined to a point of R by a curve, all of whose points
that differ from x belong to R.
Definition 1.34
Figure 2 : The regions of k4 and their
boundaries
Figure 2 shows the regions of k4
along with their boundaries. Region R1 is bounded by vertex 1 ,
edge ( 1, 2), vertex 2, edge (
2,4), vertex 4 and edge ( 4, 1 ). The other region boundaries can be determined
similarly. Notice that there is an exterior region, R4. It is bounded by vertex 1 , edge ( 1, 3 ), vertex 3, edge ( 3,
2 ), vertex 2, and edge ( 2,1 ).
Definition 1.35
The crossing number V ( G ) of a graph G is the
minimum number of edge crossings among the drawings of G in the plane.
Definition 1.36
A minimal graph G is a graph with the minimum
number of edge crossings among the drawings of G.
Definition 1.37
The rectilinear crossing number of a graph G, denoted
v( G ), is the minimum number of edge crossings among all drawings of G in the
plane in which each edge is straight line segment.
Definition 1.38
The genus of a graph G is the smallest genus of
all surfaces on which G can be embedded. The genus of a graph is denoted gen ( G ).
No comments:
Post a Comment