Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 56 for “"Independence Number"”.
-
INDEPENDENCE NUMBER OF SPECIFIED I-GRAPHS
In this paper, we study the independence number of various classes of I-graphs. I-graphs are generalizations of the Generalized Petersen Graphs. We provide constructions of independent sets given any parameters, as well as bounds for some subclasses of I-graphs. We also prove exact results for some …
-
Bounds for the independence number of a graph
The independence number of a graph is the maximum number of vertices from the vertex set of the graph such that no two vertices are adjacent. We systematically examine a collection of upper bounds for the independence number to determine graphs for which each upper bound is better than any other …
-
Minimum independence number of graphs with specified degree sequences
… thesis we consider the lower bound on a graph's independence number in terms of the degree sequence of the graph. We present three functions of the degree sequence which are known lower bounds on independence number and compare them. We show that one of these functions, the residue, is often best …
-
On the 𝑘-Independence Number and Laplacian Toughness of Graphs
… graph parameters. This work focuses on themes of independence number, connectivity, graph toughness, and closed walks in infinite regular trees. Computing the 𝑘-independence number of a graph, which is the size of a largest set of vertices that are a distance greater than 𝑘 apart in the graph, is …
-
A Horizontal Edges Bound for the Independence Number of a Graph
The independence number alpha of a graph is the size of a maximum independent set of vertices. An independent set is a set of vertices where every pair of vertices in non-adjacent. This number is known to be hard to compute. The bound we worked with is defined as epsilon = max[e(v)-eh(v)] over all …
-
AUTOMATED CONJECTURING ON THE INDEPENDENCE NUMBER AND MINIMUM DEGREE OF DIAMETER-2-CRITICAL GRAPHS
… of D2C graphs, focusing mainly on their independence number and minimum degree. We show that there exist D2C graphs with minimum degree strictly larger than their independence number, and that this gap can be arbitrarily large. We also exhibit D2C graphs with maximum number of common …
-
Boundary Independent Broadcasts in Graphs
… broadcast on $G$, called the \textit{lower bn-independence number}, is denoted $i_{bn}(G)$. The \textit{lower h-independence number} $i_h(G)$ is defined analogously for hearing independent broadcasts. We prove that $i_{bn}(G)\leq i_h(G)$ for all graphs $G$, and show that $i_h(G)/i_{bn}(G)$ is …
-
Broadcast independence and broadcast packing
… vertex hears more than one vertex. The broadcast independence number, respectively the broadcast packing number, is the maximum weight over all independent broadcasts, respectively packing broadcasts, on G. In this thesis, we examine these two broadcast parameters in different classes of graphs. …
-
STRUCTURAL PROPERTIES OF I-GRAPHS: THEIR INDEPENDENCE NUMBERS AND CAYLEY GRAPHS
We discuss in this paper the independence numbers and algebraic properties of I-graphs. The I-graphs are a further generalization of the Generalized Petersen graphs whose independence numbers have been previously researched. Specifically, we give bounds for the independence number of different …
-
Graph width parameters: from structure to algorithm
… width parameter p is a function that assigns a number to each graph G, where a small value of p(G) usually means that the graph G is "easily decomposable" with respect to the parameter p. We use graph width parameters to show that certain graphs are "easily decomposable" with respect to specific …
-
Problems in Graph Theory With Applications to Topology and Modeling RNA
… a graph $G$. We establish upper bounds for the number of vertices required to percolate in the case that $r=2$ for particular classes of graphs. In the second project, we study the structure of graphs with independence number two. We prove a lower bound on the number of edges of such graphs, …
-
Quantum independence and chromatic numbers
… thesis we are studying the cases when quantum independence and quantum chromatic numbers coincide with or differ from their classical counterparts. Knowing about the relation of chromatic numbers separation to the projective Kochen-Specker sets, we found an analogous characterisation for the …
-
Optimization on products of combinatorial structures
… structures with a product form. The independence number of a graph G, denoted $\alpha (G)$, is the size of the largest independent set in G, where a subset S of the vertex set V(G) is independent if no two vertices in S are adjacent in G. The clique covering number of G, denoted …
-
Supereulerian Properties in Graphs and Hamiltonian Properties in Line Graphs
… by Chvatal and Erdos, using the relation of independence number and connectivity as sufficient conditions for hamiltonicity of graphs, we characterize supereulerian graphs with small matching number, which implies a characterization of hamiltonian claw-free graph with small independence …
-
Paley Graphs, Prime Graphs, and Crossword Puzzles
… subgraphs. The main is to better understand the “independence structure” of the Paley graph itself. No good upper bound on the independence number of Paley graphs is known. Theorems about these subgraphs, and various counts aim at future improvement of upper bounds for the independence number of …
-
Extremal graph theory: Ramsey-Turán numbers, chromatic thresholds, and minors
… integer, and f(n) a function. The t-Ramsey-Turan number of H, RT_t(n,H,f(n)), is the maximum number of edges in an n-vertex, H-free graph with K_t-independence number less than f(n), where the K_t-independence number of a graph G is the maximum number of vertices in a K_t-free induced graph of G. …
-
Properties of Small Ordered Graphs Whose Vertices are Weighted by Their Degree
… degree. We find the vertex weighted domination number in connected graphs, beginning with trees, and we define how weighted vertices can affect eccentricity, independence number, and connectivity.
-
The Minimum Witt Index of a Graph
… of an independent set in G is called the independence number. Given a graph G and weight matrix A of G with entries from some field F, the maximum dimension of an A-isotropic subspace, known as the Witt index of A, is an upper bound on alpha(G). Since any weight matrix can be used, it is …
-
INFLUENCE OF SELECTED ECONOMIC, DEMOGRAPHIC AND POLITICAL CHARACTERISTICS ON GROWTH IN AFRICA
… influenced on growth in Africa. Judicial independence, number of days to start business and reliability of financial institutions did not show significant influence on growth in Africa. To promote growth, African governments need to redesign their education systems in order to be able to …
-
KE Theory & the Number of Vertices Belonging to All Maximum Independent Sets in a Graph
… of a maximum matching and let $\xi (G)$ be the number of vertices belonging to all maximum independent sets. Boros, Golumbic and Levit showed that in connected graphs where the independence number $\alpha (G)$ is greater than the matching number $\mu (G)$, $\xi (G) \geq 1 + \alpha(G) - \mu (G)$. …
Page 1 of 3