Question

In: Advanced Math

(c) Deduce that the Horton graph (p. 240) is nonhamiltonian.

(c) Deduce that the Horton graph (p. 240) is nonhamiltonian.

Solutions

Expert Solution

In the mathematical field of graph theory, the Horton graph or Horton 96-graph is a 3-regular graph with 96 vertices and 144 edges discovered by Joseph Horton. Published by Bondy and Murty in 1976, it provides a counterexample to the Tutte conjecture that every cubic 3-connected bipartite graph is Hamiltonian.

After the Horton graph, a number of smaller counterexamples to the Tutte conjecture were found. Among them are a 92 vertex graph by Horton published in 1982, a 78 vertex graph by Owens published in 1983, and the two Ellingham-Horton graphs (54 and 78 vertices).

The first Ellingham-Horton graph was published by Ellingham in 1981 and was of order 78.At that time, it was the smallest known counterexample to the Tutte conjecture. The second one was published by Ellingham and Horton in 1983 and was of order 54. In 1989, Georges' graph, the smallest currently-known non-Hamiltonian 3-connected cubic bipartite graph was discovered, containing 50 vertices.

As a non-Hamiltonian cubic graph with many long cycles, the Horton graph provides good benchmark for programs that search for Hamiltonian cycles.The Horton graph has chromatic number 2, chromatic index 3, radius 10, diameter 10, girth 6, book thickness 3[10] and queue number 2[10]. It is also a 3-edge-connected graph.

Algebraic properties

The automorphism group of the Horton graph is of order 96 and is isomorphic to Z/2Z×Z/2Z×S4, the direct product of the Klein four-group and the symmetric group S4.


Related Solutions

The PV diagram of an adiabatic expansion, the graph of P= CV-γ, where C is a...
The PV diagram of an adiabatic expansion, the graph of P= CV-γ, where C is a constant and γ = Cp/Cv. GOAL Use the adiabatic pressure vs. volume relation to find a change in pressure and the work done on a gas. PROBLEM A monatomic ideal gas at an initial pressure of 1.01  105 Pa expands adiabatically from an initial volume of 1.50 m3, doubling its volume. (a) Find the new pressure. (b) Sketch the PV diagram and estimate the work...
Give an example of a graph G with p(G) = 7 and c(G) = 3.
Give an example of a graph G with p(G) = 7 and c(G) = 3.
Let S = {a, b, c}. Draw a graph whose vertex set is P(S) and for...
Let S = {a, b, c}. Draw a graph whose vertex set is P(S) and for which the subsets A and B of S are adjacent if and only if A ⊂ B and |A| = |B| − 1. (a) How many vertices and edges does this graph have? (b) Can you name this graph? (c) Is this graph connected? (d) Does it have a perfect matching? If yes, draw a sketch of the matching. (e) Does it have a...
If n = 240 and ˆ p (p-hat) = 0.7, construct a 99% confidence interval. Give...
If n = 240 and ˆ p (p-hat) = 0.7, construct a 99% confidence interval. Give your answers to three decimals < p <
Interpret the following results: 1. Dr. Horton conducted a study and reported: p = .001, d...
Interpret the following results: 1. Dr. Horton conducted a study and reported: p = .001, d = .40. Dr. Theimer conducted a similar study and reported: p =.04, d = .40. Who had the larger effect and what is the most likely reason they had different p-values? 2. Dr. Lane reported that following a study on the effects of a new drug on obsessive compulsive disorder (OCD), that the F for the drug was p = .03. Dr. Lane concluded...
The inverse demand for the monopolist's output is P = 240 − 20q and its marginal...
The inverse demand for the monopolist's output is P = 240 − 20q and its marginal cost is MC = 40. Find the prot maximizing price (Pm) and the quantity for the monopolist (qm). If the demand and marginal cost functions in question belonged above to a perfectly competitive rm, what would be the price (Ppc) and the quantity (qpc)? What is the deadweight loss due to the monopoly?
The inverse demand function for video games is p = 240 ? 2q and the inverse...
The inverse demand function for video games is p = 240 ? 2q and the inverse supply function is p = 3 + q. The government imposes a $6 tax on each video game purchased. a) Find CS and PS before tax b. Find CS and PS after tax c. Does the CS fall by more than the PS or not? (SHOW THE PROOF USING VALUES OF ELASTICITES OF DEMAND AND SUPPLY)
Demand for education is characterized by the following equation: P = 240 – 4Q. The marginal...
Demand for education is characterized by the following equation: P = 240 – 4Q. The marginal private cost of education is P = 40 + 6Q. Production of education also creates a per unit positive externality equal to 2Q. Suppose that the market is currently unregulated (i.e., the positive externality is not currently being corrected for in the market). What is output and price? The marginal social benefit (MSB) accounts for the marginal private benefit of production as well as...
P(A) = 0.78, P(B) = 0.75, P(C) = 0.18, P(A∩B) = 0.67, P(A∩C) = 0.15, P(B∩C)...
P(A) = 0.78, P(B) = 0.75, P(C) = 0.18, P(A∩B) = 0.67, P(A∩C) = 0.15, P(B∩C) = 0.12, P(A∩B∩C) = 0.11. Find: 1. Find P(A∪B∪C) 2. Find P((A∩B)∪C) 3. Find P(A∩(B∪C))
Given the following information QD = 240 - 5P QS = p where QD is the...
Given the following information QD = 240 - 5P QS = p where QD is the quantity demand, QS is the quantity supplied and P is the price. Find: a) Equilibrium price before the tax. b) Equilibrium quantity before the tax c) Buyers reservation price d)Seller's reservation price e) Consumer surplus before tax f)Producer surplus before tax
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT