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 36 for “"Critical graphs"”.

  1. Independent domination critical graphs

    … of 𝘎. We study several different definitions of graphs which are critical with respect to the domination number (respectively, independent domination number), and give examples of infinite families of graphs of each type. Comparing these families leads to four principal types of critical graphs, …

    uvic Repository record for Independent domination critical graphs (opens in a new tab)

  2. Ultraconnected and Critical Graphs

    We investigate the ultraconnectivity condition on graphs, and provide further connections between critical and ultraconnected graphs in the positive definite partial matrix completion problem. We completely characterize when the join of graphs is ultraconnected, and prove that ultraconnectivity is …

    byu Repository record for Ultraconnected and Critical Graphs (opens in a new tab) Download PDF for Ultraconnected and Critical Graphs (opens in a new tab)

  3. Double Domination Edge Critical Graphs.

    … number. A graph G is double domination edge critical if for any edge uv ∈ E(G̅), the double domination number of G+uv is less than the double domination number of G. We investigate properties of double domination edge critical graphs. In particular, we characterize the double domination edge …

    etsu Repository record for Double Domination Edge Critical Graphs. (opens in a new tab) Download PDF for Double Domination Edge Critical Graphs. (opens in a new tab)

  4. Color-critical graphs on surfaces

    A graph is (t+1)-critical if it is not t-colorable, but every proper subgraph is. In this thesis, we study the structure of critical graphs on higher surfaces. One major result in this area is Carsten Thomassen's proof that there are finitely many 6-critical graphs on a fixed surface. This proof …

    gatech Repository record for Color-critical graphs on surfaces (opens in a new tab)

  5. Investigation of 4-cutwidth critical graphs

    … Math characterized the set of a 3-cutwidth critical graphs by five specified elements. This project extends the idea to 4-cutwidth critical graphs.

    csusb Repository record for Investigation of 4-cutwidth critical graphs (opens in a new tab)

  6. Investigation of 4-cutwidth critical graphs

    … Math characterized the set of a 3-cutwidth critical graphs by five specified elements. This project extends the idea to 4-cutwidth critical graphs.

    csusb-retro Repository record for Investigation of 4-cutwidth critical graphs (opens in a new tab)

  7. Density and Structure of Homomorphism-Critical Graphs

    Let $H$ be a graph. A graph $G$ is $H$-critical if every proper subgraph of $G$ admits a homomorphism to $H$, but $G$ itself does not. In 1981, Jaeger made the following conjecture concerning odd-cycle critical graphs: every planar graph of girth at least $4t$ admits a homomorphism to $C_{2t+1}$ …

    waterloo Repository record for Density and Structure of Homomorphism-Critical Graphs (opens in a new tab)

  8. Going critical : an investigation of diameter -critical graphs

    … maximum degree D, and diameter d, to be d-critical if it has the property that for any edge e G E, the graph G — e has diameter > d. We explore some results relating to a conjecture on the maximum possible number of edges in a 2-critical graph. We also present efficient algorithms for …

    ubc Repository record for Going critical : an investigation of diameter -critical graphs (opens in a new tab) Download PDF for Going critical : an investigation of diameter -critical graphs (opens in a new tab)

  9. Sparsity in Critical Graphs with Small Clique Number

    … increasingly large values of $\varepsilon$ in graphs with sufficiently large maximum degree. One of the main lemmas used in deriving these bounds states that graphs which are list-critical are sparse. This result generally follows by applying a sufficient condition for list colouring complete …

    waterloo Repository record for Sparsity in Critical Graphs with Small Clique Number (opens in a new tab)

  10. 2-crossing critical graphs with a V8 minor

    … drawings of the graph. A graph G is k-crossing critical if it has crossing number k and any proper subgraph of G has a crossing number less than k. The set of 1-crossing critical graphs is is determined by Kuratowski’s Theorem to be {K5, K3,3}. Work has been done to approach the problem of …

    waterloo Repository record for 2-crossing critical graphs with a V8 minor (opens in a new tab)

  11. On 2-crossing-critical graphs with a V8-minor

    … drawing of a graph. A graph $G$ is $k$-crossing-critical if it has crossing number at least $k$, and any subgraph of $G$ has crossing number less than $k$. A consequence of Kuratowski's theorem is that 1-critical graphs are subdivisions of $K_{3,3}$ and $K_{5}$. The graph $V_{2n}$ is a $2n$-cycle …

    waterloo Repository record for On 2-crossing-critical graphs with a V8-minor (opens in a new tab)

  12. Sparse color-critical graphs and rainbow matchings in edge-colored graphs

    Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-04-05T19:14:32Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 26 THESIS_04.tex: 303472 bytes, checksum: ac02fb44aef43edf6047cfd6a308c01b (MD5) Setup.pdf: 26974 bytes, checksum: …

    uiuc Repository record for Sparse color-critical graphs and rainbow matchings in edge-colored graphs (opens in a new tab)

  13. Analyzing Tree Attachments in 2-Crossing-Critical Graphs with a V8 Minor

    … the graph in the plane. A graph G is k-crossing-critical if its crossing number is at least k and if every proper subgraph H of G has crossing number less than k. It follows directly from Kuratowski's Theorem that the 1-crossing-critical graphs are precisely the subdivisions of K{3,3} and K5. …

    waterloo Repository record for Analyzing Tree Attachments in 2-Crossing-Critical Graphs with a V8 Minor (opens in a new tab)

  14. AUTOMATED CONJECTURING ON THE INDEPENDENCE NUMBER AND MINIMUM DEGREE OF DIAMETER-2-CRITICAL GRAPHS

    A diameter-2-critical (D2C) graph is a graph with diameter two such that removing any edge increases the diameter or disconnects the graph. In this paper, we look at other lesser-studied properties of D2C graphs, focusing mainly on their independence number and minimum degree. We show that there …

    vcu Repository record for AUTOMATED CONJECTURING ON THE INDEPENDENCE NUMBER AND MINIMUM DEGREE OF DIAMETER-2-CRITICAL GRAPHS (opens in a new tab)

  15. Extremal Problems in Graph Theory: Hamiltonicity, Minimum Vertex -Diameter -2 -Critical Graphs and Decomposition

    … graph K n can be decomposed into k spanning subgraphs with the t-star property. We prove that ift≥3and k≥68+t,then ft,k ≥32˙2 tk+25-10t ˙2t-2-3. .

    uiuc Repository record for Extremal Problems in Graph Theory: Hamiltonicity, Minimum Vertex -Diameter -2 -Critical Graphs and Decomposition (opens in a new tab)

  16. The chromatic index of simple graphs

    … (i) to study the structural properties of graphs which are critical with respect to edge-colourings; (ii) to apply the results obtained to the classification problem arising from Vizing's Theorem. Chapter 1 contains a historical, non-technical introduction, general graph-theoretic …

    the-open-u Download PDF for The chromatic index of simple graphs (opens in a new tab)

  17. Vertex-Criticality and Bicriticality for Independent Domination and Total Domination in Graphs

    … is said to be independent domination vertex-critical, or i-critical, if the removal of any vertex decreases the independent domination number. Likewise, a graph is said to be total domination vertex-critical if the removal of any vertex decreases the total domination number. Following these …

    uvic Repository record for Vertex-Criticality and Bicriticality for Independent Domination and Total Domination in Graphs (opens in a new tab)

  18. On the linear vertex arboricity of graphs

    … arboricity of various classes of simple graphs are determined. In particular, the joins of various types of graphs turn out to provide nice structures that are related to their linear vertex arboricity. The characterization of maximally critical graphs (graphs of which the linear vertex …

    nus Repository record for On the linear vertex arboricity of graphs (opens in a new tab) Download file for On the linear vertex arboricity of graphs (opens in a new tab)

  19. Two Results in Drawing Graphs on Surfaces

    In this work we present results on crossing-critical graphs drawn on non-planar surfaces and results on edge-hamiltonicity of graphs on the Klein bottle. We first give an infinite family of graphs that are 2-crossing-critical on the projective plane. Using this result, we construct …

    lsu-thes Repository record for Two Results in Drawing Graphs on Surfaces (opens in a new tab)

Page 1 of 2