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 16 of 16 for “"Matching Number"”.
-
Matchings, Connectivity, and Eigenvalues in Regular Graphs
… 2, we obtain the best lower bound for the matching number over $n$-vertex connected regular graphs in terms of edge-connectedness and determine when the matching number is minimized. We also establish the best upper bound for the number of cut-edges over $n$-vertex connected odd regular …
-
Coloring Algorithms for Graphs and Hypergraphs with Forbidden Substructures
… hypergraphs with bounded edge size and bounded matching number, as well as the $r$-Pre-Coloring Extension Problem in hypergraphs with uniform edge size and bounded matching number. We also get partial complexity result of the $r$-Coloring Problem in hypergraphs with uniform edge size and bounded …
-
Homogeneous sets in graphs and hypergraphs
… distance. We use this model to determine a number of properties of random perfect graphs, including the distribution of the stability and the clique number, the probability of containing a fixed induced subgraph, Hamiltonicity, clique-colourability, connectivity, edge colouring, and the …
-
KE Theory & the Number of Vertices Belonging to All Maximum Independent Sets in a Graph
… let $\mu (G)$ be the cardinality 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 …
-
Computing and Bounding the Scattering Number of Graphs
In this thesis we study the scattering number of graphs, a parameter introduced by Jung in 1978, from two different perspectives. First, we investigate it under a computational lens, proving that the scattering number of bipartite and planar graphs cannot be computed in polynomial time unless P=NP, …
-
Homological invariants of some special varieties
… some homological invariants (e.g., graded Betti numbers, Hilbert function, regularity) of some special varieties. In particular, we focus on the codimension two ACM varieties in P1×P1×P1 (called varieties of lines), and the edge ideals of bicyclic graphs. We study the Hilbert function of Ferrers …
-
On the Regularity of Powers of Edge Ideals
… H. T. Ha, and T. N. Trung [2] expands on the number of cases known by showing, for all powers of a forest and all powers greater than 1 of a cycle, reg(J8) = 2x·+ v(G) - 1 where v(G) is the induced matching number for the graph G. The purpose of this paper is to fill in the details of [2] and …
-
Supereulerian Properties in Graphs and Hamiltonian Properties in Line Graphs
… 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 number.;We also …
-
CONTENT BASED SEARCH OF MECHANICAL ASSEMBLIES
… consists of exact and approximate string matching, number matching and computing graph compatibility. Various research groups have solved the former two problems. This thesis describes a new algorithm to solve graph compatibility problem using branch and bound search. The performance of …
-
Extremal Hypergraphs for Ryser's Conjecture
… $\nu(\mathcal{H})$ represent the vertex cover number and the matching number, respectively. The conjecture is still wide open, though advances in various directions have been made by Aharoni, Berger, F\"uredi, Haxell, Lov{\'a}sz, Mansour, Scott, Song, Tuza, Yuster, and Ziv, among others. In …
-
On Supereulerian Digraphs
… we discussed it for the following conditions.;1. Matching number condition. Let D be a digraph and G be a graph. Let lambda(D) be the arc-strong connectivity of D, alpha(D) be the independence number of D, alpha'(D) be the size of a maximum matching of D, and kappa'(G) be the edge conectivity of …
-
Games on graphs, visibility representations, and graph colorings
… nonnegative integer to each vertex of V(G). An f-matching in G is a set M ⊆ E(G) such that the number of edges of M incident to v is at most f(v) for all v ⊆ V(G). In the f-matching game on a graph G, denoted (G,f), players Max and Min alternately choose edges of G to build an f-matching; the game …
-
Spanning Trails and Spanning Trees
… kappa( G) and kappa'(G) denote the independence number, the matching number, connectivity and edge connectivity of a graph G, respectively. First, we discuss the 3-edge-connected graphs with bounded edge-cuts of size 3, and prove that any 3-edge-connected graph with at most 11 edge cuts of size 3 …
-
A study on supereulerian digraphs and spanning trails in digraphs
… such that for any strong digraph D with its matching number α′(D) and arc-strong-connectivity λ(D), if n = |V (D)| ≥ 3 and λ(D) ≥ α′(D) − 1, then each of the following holds. (i) There exists a family D of well-characterized digraphs such that for any digraph D with α′(D) ≤ 2, D has a …
-
Weighted Modulo Orientations of Graphs
… finite many exceptions for graphs with bounded matching numbers not admitting any modulo (2k+1)-orientations for any positive integers t. We additionally characterize all infinite many graphs with bounded matching numbers but without a nowhere-zero 3-flow. This partially supports Jaeger's …
-
On Eulerian subgraphs and hamiltonian line graphs
… and $L(G)$ denote the minimum degree, the matching number and the line graph of a graph $G$, respectively. The following result is obtained. {\color{black} Let $G$ be a simple graph} with $|E(G)| \ge 3$. If $\delta(G) \geq \alpha'(G)$, then each of the following holds. \\ (i) $L(G)$ is …