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 14 of 14 for “"cubic graph"”.

  1. Minimum Conditions for Bootstrap Percolation on the Cubic Graph

    … is an iterative process on the vertices of a graph. Initially, a proper, non-empty set of vertices is infected, and all other vertices are uninfected. At each iteration, every uninfected vertex with a certain number of infected neighbors becomes infected, and all infected vertices remain so …

    texas-state Repository record for Minimum Conditions for Bootstrap Percolation on the Cubic Graph (opens in a new tab)

  2. Surjectivity of the Wahl Map on Cubic Graphs

    … curve. We simplify this problem by converting graph curves to dual graphs. Then the information for graphs can be used to study the underlying curves. We will discuss conditions for the Wahl map to be surjective on a cubic graph. The Wahl map on a cubic graph has two parts, one map onto the …

    uky-thes Repository record for Surjectivity of the Wahl Map on Cubic Graphs (opens in a new tab)

  3. Perfect Matching and Circuit Cover of Graphs

    … and independently Seymour, that every bridgeless graph G has a family of circuits which covers every edge of G twice. By Fleischner's Splitting Lemma, it suffices to verify the circuit double cover conjecture for bridgeless cubic graphs.;It is well known that every edge-3-colorable cubic graph has …

    wvu Repository record for Perfect Matching and Circuit Cover of Graphs (opens in a new tab)

  4. Circuits, Perfect Matchings and Paths in Graphs

    … a family of circuits to cover a bidgeless graph (mainly on cubic graph) with respect to a given weight function defined on the edge set. The first chapter of this thesis is going to cover all basic concepts and notations will be used and a survey of this topic.;In Chapter two, we shall pay …

    wvu Repository record for Circuits, Perfect Matchings and Paths in Graphs (opens in a new tab)

  5. Chords of longest circuits of graphs

    … Thomassen: Every longest circuit of 3-connected graph has a chord. In 1987, C. Q. Zhang proved that every longest circuit of a 3-connected planar graph G has a chord if G is cubic or if the minimum degree is at least 4. In 1997, Carsten Thomassen proved that every longest circuit of 3-connected …

    wvu Repository record for Chords of longest circuits of graphs (opens in a new tab)

  6. Some results on cubic graphs

    … Oxley, we investigate whether the edge set of a graph admits a bipartition so that the contraction of either partite set produces a series-parallel graph. While Oxley's question in general remains unanswered, our investigations led to two graph operations (Chapters 2 and 4) which are of …

    lsu-thes Repository record for Some results on cubic graphs (opens in a new tab)

  7. Aspects of graph colouring

    … ways of measuring different aspects of graphs are presented, in particular, the ‘colouring difference’ between two edge-colourings of a graph (Chapter 5) and the ‘beta parameter’ (defined in Chapter 2 and used in Chapters 3 and 6); this is a measure of how far from a type 1 graph a type …

    the-open-u Download PDF for Aspects of graph colouring (opens in a new tab)

  8. The computational complexity of edge colouring restricted graphs

    Edge colouring a graph is a classic algorithmi,; graph problem which has many applications. The problem of determining the chnmatic index is, in general, NP­-complete. This thesis investigates the computational complexity of edge colouring restricted graphs. Previous work has established that the …

    uvic Repository record for The computational complexity of edge colouring restricted graphs (opens in a new tab)

  9. Approximate edge 3-coloring of cubic graphs

    … edge 3-coloring polynomial time algorithm for cubic graphs. For any cubic graph with n vertices, using this coloring algorithm, we get an edge 3-coloring with at most n/3 error vertices. In the second part, we study Jim Propp's Rotor-Router model on some non-bipartite graph. We find the …

    gatech Repository record for Approximate edge 3-coloring of cubic graphs (opens in a new tab)

  10. Entropy and Graphs

    The entropy of a graph is a functional depending both on the graph itself and on a probability distribution on its vertex set. This graph functional originated from the problem of source coding in information theory and was introduced by J. K\"{o}rner in 1973. Although the notion of graph entropy …

    waterloo Repository record for Entropy and Graphs (opens in a new tab)

  11. Towards New Bounds for the 2-Edge Connected Spanning Subgraph Problem

    Given a complete graph K_n = (V,E) with non-negative edge costs c ∈ R^E, the problem multi-2EC_cost is that of finding a 2-edge connected spanning multi-subgraph of K_n with minimum cost. It is believed that there are no efficient ways to solve the problem exactly, as it is NP-hard. Methods such as …

    ottawa-retro Repository record for Towards New Bounds for the 2-Edge Connected Spanning Subgraph Problem (opens in a new tab)

  12. Uniform multicommodity flows in random networks

    … a model is considered in which the underlying graph is fixed and the edge capacities are random. Aldous, McDiarmid and Scott studied the case in which the underlying graph is complete, the edge capacities are independent, each distributed like a given random variable <em>C</em>, and &Vscr; is …

    oxford Restricted access

  13. Finding a Second Hamiltonian cycle in Barnette Graphs

    … and (2) finding a second Hamiltonian cycle in cubic graphs. The existence of solution for both problems is guaranteed by a parity argument. For the first problem we prove that deciding whether a 2-oik has a room-partitioning is NP-hard, even if the 2-oik corresponds to a planar triangulation. …

    waterloo Repository record for Finding a Second Hamiltonian cycle in Barnette Graphs (opens in a new tab)