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"”.
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 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 …
-
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 …
-
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 …
-
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 …
-
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 𝒱 is …
-
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. …