Prove that if diam(G)=3 for a regular graph G, then d i a m ( <mrow class="MJX-Te

Mayra Berry 2022-06-10 Answered
Prove that if diam(G)=3 for a regular graph G, then d i a m ( G ¯ ) = 2..
I know that without using regularity one can show that if d i a m ( G ) 3 , then  d i a m ( G ¯ ) 3. How do I use regularity to show that it must be exactly 2?
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Punktatsp
Answered 2022-06-11 Author has 22 answers
Suppose G is a graph with diam(G)>2 and d i a m ( G ¯ ) > 2 ;; I will show that G is not regular.
More precisely, let x , y , v , w be vertices with d G ( x , y ) > 2 and d G ¯ ( v , w ) > 2 ;; I will show that deg ( v ) + deg ( w ) > deg ( x ) + deg ( y ) ,, the degrees being computed in G.
Clearly x , y , v , w are four distinct vertices, v w E ( G ) , and x y E ( G ¯ ) . Since d G ¯ ( v , w ) > 2 , at least one of the edges x v , x w is in E(G); without loss of generality, we assume that x v E ( G ) . It readily follows that y v E ( G ¯ ) ,   y w E ( G ) ,, and x w E ( G ¯ ) ..
Let S = V ( G ) { x , y , v , w } .. Let m be the number of edges (of G) between S and { v , w } ,, and let n be the number of edges between S and {x,y}. Then deg ( v ) + deg ( w ) = m + 4 ,, and deg ( x ) + deg ( y ) = n + 2.
Since each vertex in S is joined (by an edge of G) to at least one vertex in { v , w } and to at most one vertex in {x,y}, we have m n ;; it follows that
deg ( v ) + deg ( w ) = m + 4 > n + 2 = deg ( v ) + deg ( w ) .
Not exactly what you’re looking for?
Ask My Question

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2022-07-18
Which of the following statements about the effect size is CORRECT?
a. the effect size is bigger when the two populations overlap more.
b. The effect size is NOT affected by the differences between means.
c. Standard effect size is always positive, because it is figured using the square root.
d. The effect size is bigger when the standard deviation of population gets smaller.
asked 2022-06-17
What is an independent variable in chemistry?
asked 2022-04-07
What is a latent variable?
asked 2022-07-20
When you look up the probability in a z-table is that the value less than or less than or equal?
For example is it p ( z < 2.35 ) = .0094 or is it p ( z 2.35 ) = .0094?
And if they aren't equal then how would you calculate the other one?
I would think given any single point has 0 width that it shouldn't matter, but I am not sure.
asked 2022-07-21
How does the shielding effect affect atomic radius?
asked 2022-06-16
The proportion of people who like playing basketball is 2%, so a student randomly sample 1000, but find the proportion is 4%, if the true proportion is 2%. What the probability that this student detect at least 4% in random sample?
I used the formula, but found the z score is 4.51 which is impossible I think.
asked 2022-06-27
Suppose that X 1 , X 2 , , X n are IID Bernoulli random variables with success probability equal to an unknown parameter θ [ 0 , 1 ].
Let A and B be nonnegative constants. If we impose the prior π ( θ ) ( θ a ) ( ( 1 θ ) b ), then what is the Bayesian posterior mode?

New questions

The Porsche Club of America sponsors driver education events that provide high-performance driving instruction on actual racetracks. Because safety is a primary consideration at such events, many owners elect to install roll bars in their cars. Deegan Industries manufactures two types of roll bars for Porsches. Model DRB is bolted to the car using existing holes in the car's frame. Model DRW is a heavier roll bar that must be welded to the car's frame. Model DRB requires 20 pounds of a special high alloy steel, 40 minutes of manufacturing time, and 60 minutes of assembly time. Model DRW requires 25 pounds of the special high alloy steel, 100 minutes of manufacturing time, and 40 minutes of assembly time. Deegan's steel supplier indicated that at most 40,000 pounds of the high-alloy steel will be available next quarter. In addition, Deegan estimates that 2000 hours of manufacturing time and 1600 hours of assembly time will be available next quarter. The pro?t contributions are $200 per unit for model DRB and $280 per unit for model DRW. The linear programming model for this problem is as follows:
Max 200DRB + 280DRW
s.t.
20DRB + 25DRW 40,000 Steel Available
40DRB + 100DRW ? 120,000 Manufacturing minutes
60DRB + 40DRW ? 96,000 Assembly minutes
DRB, DRW ? 0
Optimal Objective Value = 424000.00000
Variable Value blackuced Cost
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
DRB 1000.00000 0.00000
DRW 800.00000 0.00000
Constraint Slack/ Surplus Dual Value
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 0.00000 8.80000
2 0.00000 0.60000
3 4000.00000 0.00000
Objective Allowable Allowable
Variable Coef?cient Increase Decrease
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
DRB 200.00000 24.00000 88.00000
DRW 280.00000 220.00000 30.00000
RHS Allowable Allowable
Constraint Value Increase Decrease
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 40000.00000 909.09091 10000.00000
2 120000.00000 40000.00000 5714.28571
3 96000.00000 Infnite 4000.00000
a. What are the optimal solution and the total profit contribution?
b. Another supplier offeblack to provide Deegan Industries with an additional 500 pounds of the steel alloy at $2 per pound. Should Deegan purchase the additional pounds of the steel alloy? Explain.
c. Deegan is considering using overtime to increase the available assembly time. What would you advise Deegan to do regarding this option? Explain.
d. Because of increased competition, Deegan is considering blackucing the price of model DRB such that the new contribution to profit is $175 per unit. How would this change in price affect the optimal solution? Explain.
e. If the available manufacturing time is increased by 500 hours, will the dual value for the manufacturing time constraint change? Explain.