Certain graphs can be described by the distribution of the edges in its subgraphs.
For example, a cycle C is a graph that satisfies |E(H)|
|V (H)| < |E(C)|
|V (C)| = 1 for all non-trivial
subgraphs of C. Similarly, a tree T is a graph that satisfies |E(H)|
|V (H)|−1 ≤ |E(T)|
|V (T)|−1 = 1
for all non-trivial subgraphs of T. In general, a balanced graph G is a graph such
that |E(H)|
|V (H)| ≤ |E(G)|
|V (G)| and a 1-balanced graph is a graph such that |E(H)|
|V (H)|−1 ≤ |E(G)|
|V (G)|−1
for all non-trivial subgraphs of G. Apart from these, for integers k and l, graphs G
that satisfy the property |E(H)| ≤ k|V (H)| − l for all non-trivial subgraphs H of G
play important roles in defining rigid structures.
This dissertation is a formal study of a class of density functions that extends the
above mentioned ideas. For a rational number r ≤ 1, a graph G is said to be r-balanced
if and only if for each non-trivial subgraph H of G, we have |E(H)|
|V (H)|−r ≤ |E(G)|
|V (G)|−r . For
r > 1, similar definitions are given. Weaker forms of r-balanced graphs are defined
and the existence of these graphs is discussed. We also define a class of vulnerability
measures on graphs similar to the edge-connectivity of graphs and show how it is
related to r-balanced graphs. All these definitions are matroidal and the definitions
of r-balanced matroids naturally extend the definitions of r-balanced graphs.
The vulnerability measures in graphs that we define are ranked and are lesser
than the edge-connectivity. Due to the relationship of the r-balanced graphs with
the vulnerability measures defined in the dissertation, identifying r-balanced graphs
and calculating the vulnerability measures in graphs prove to be useful in the area of network survivability. Relationships between the various classes of r-balanced
matroids and their weak forms are discussed. For r ∈ {0, 1}, we give a method to
construct big r-balanced graphs from small r-balanced graphs. This construction is a
generalization of the construction of Cartesian product of two graphs. We present an
algorithmic solution of the problem of transforming any given graph into a 1-balanced
graph on the same number of vertices and edges as the given graph. This result is
extended to a density function defined on the power set of any set E via a pair of
matroid rank functions defined on the power set of E. Many interesting results may
be derived in the future by choosing suitable pairs of matroid rank functions and
applying the above result.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-2533 |
| Date | 15 May 2009 |
| Creators | Kannan, Lavanya |
| Contributors | Hobbs, Arthur M |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Dissertation, text |
| Format | electronic, application/pdf, born digital |
Page generated in 0.0021 seconds