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"”.

  1. 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 …

    uiuc Repository record for Matchings, Connectivity, and Eigenvalues in Regular Graphs (opens in a new tab)

  2. 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 …

    waterloo Repository record for Coloring Algorithms for Graphs and Hypergraphs with Forbidden Substructures (opens in a new tab)

  3. 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 …

    oxford Repository record for Homogeneous sets in graphs and hypergraphs (opens in a new tab)

  4. 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 …

    vcu Repository record for KE Theory & the Number of Vertices Belonging to All Maximum Independent Sets in a Graph (opens in a new tab)

  5. 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, …

    waterloo Repository record for Computing and Bounding the Scattering Number of Graphs (opens in a new tab)

  6. 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 …

    catania Repository record for Homological invariants of some special varieties (opens in a new tab)

  7. 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 …

    texas-state Repository record for On the Regularity of Powers of Edge Ideals (opens in a new tab)

  8. 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 …

    wvu Repository record for Supereulerian Properties in Graphs and Hamiltonian Properties in Line Graphs (opens in a new tab)

  9. 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 …

    maryland Repository record for CONTENT BASED SEARCH OF MECHANICAL ASSEMBLIES (opens in a new tab)

  10. 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 …

    fu-berlin Repository record for Extremal Hypergraphs for Ryser's Conjecture (opens in a new tab)

  11. 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 …

    wvu Repository record for On Supereulerian Digraphs (opens in a new tab)

  12. 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 …

    uiuc Repository record for Games on graphs, visibility representations, and graph colorings (opens in a new tab)

  13. 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 …

    wvu Repository record for Spanning Trails and Spanning Trees (opens in a new tab)

  14. 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 …

    wvu Repository record for A study on supereulerian digraphs and spanning trails in digraphs (opens in a new tab)

  15. 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 …

    wvu Repository record for Weighted Modulo Orientations of Graphs (opens in a new tab)

  16. 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 …

    wvu Repository record for On Eulerian subgraphs and hamiltonian line graphs (opens in a new tab)