1 answer

(a) Show that 2, 3, 3, 3 is not the eccentricity sequence of any graph. (b)...

Question:

(a) Show that 2, 3, 3, 3 is not the eccentricity sequence of any graph.

(b) Determine all pairs a, b of positive integers a < b such that a, b, b, b is the eccentricity sequence of some graph.


Answers

for any two vertex p and q in a connected graph G let d(a,b) denote the distance between p and q.

(a) Let G be a connected graph of order 4 having a vertex u with eccentricity 2. Then there are vertices v and w. Such that u and w are not adjacent and u\rightarrow v\rightarrow w is a path. Let x be the vertex of G other than u, v and w. Since w must have eccentricity 3, and d(w,v)=1 and d(w,u)= 2, x must be adjacent to u and not adjacent to v and w\rightarrow v\rightarrow u\rightarrow x is a path.

But then v cannot have eccentricity 3 as its distance from any other vertex is less than 3

(b).Let G be a graph with eccentricity sequence a,b,b,b where a<b are positive integers.Since the eccentricity sequence has 4 elements G is a connected graph of order 4. Therefore we must have both a and b < 4 as the length of a path in a conncected graph is less than the order of the graph . Therefore b\leq 3 and a\leq 2 .

if a= 2 then b= 3 and we cannot have a graph in this case by the solution of the previous problem.

if a=1 then there is a vertex v of G such that d(v,s)=1 for all other vertex s of G. Thus the other 3 vertices are adjacent to v. and hence we must have b=2.

We give an example of such a graph example below

.

Similar Solved Questions

1 answer
Three male patients, TT, PP, and WW, came into a medical clinic with symptoms of lethargy...
Three male patients, TT, PP, and WW, came into a medical clinic with symptoms of lethargy (feeling tired) and chest congestion. A blood sample was taken for each patient to measure the hematocrit levels and determine their individual hemoglobin saturation curves. The results are shown in the link po...
1 answer
11. The payback period The payback method helps firms establish and identify a maximum acceptable payback...
11. The payback period The payback method helps firms establish and identify a maximum acceptable payback period that helps in capital budgeting decisions. There are two versions of the payback method: the conventional payback method and the discounted payback method Consider the following case: Gre...
1 answer
This is a biofuel made from coconut oil. Can someone identify the stretching and bonds present?
This is a biofuel made from coconut oil. Can someone identify the stretching and bonds present?...
1 answer
Question 3 (2 points) Which of the following is considered a weak acid when dissolved in...
Question 3 (2 points) Which of the following is considered a weak acid when dissolved in water? c) H2SO3 b) HF a) HNO2 A) a only B) c only C) All of them D) b only E) None of them...
1 answer
350 300 250 200 150 100 50 0 50 100 150 200 250 300 350 400...
350 300 250 200 150 100 50 0 50 100 150 200 250 300 350 400 450 500 Actual Aggregate Expenditure (Y, billions of $) Instructions: Enter whole numbers into each box a. What is the Keynesian equilibrium output in this economy? billion b. At an output level of $200 billion, planned aggregate expenditur...
1 answer
Required information [The following information applies to the questions displayed below.] Shown here are condensed inc...
Required information [The following information applies to the questions displayed below.] Shown here are condensed income statements for two different companies (assume no income taxes). Miller Company Sales $1,300,000 Variable expenses (80%) 1,040,000 Income before interest 260,000 Interest expens...
1 answer
You are helping a small yachting company understand the effects of building a new harbor on...
You are helping a small yachting company understand the effects of building a new harbor on longshore transport. Below is a sketch of how most of the waves approach the shore. The lines represent the wave crests. 1. In which direction would longshore transport carry water and sand?...
1 answer
ACTIVE LEARNING TEMPLATE: Basic Concept STUDENT NAME CONCEPT in an older adut Client REVIEW MODULE CHAPTER...
ACTIVE LEARNING TEMPLATE: Basic Concept STUDENT NAME CONCEPT in an older adut Client REVIEW MODULE CHAPTER Nursing Interventions WHO? WHEN? WHY? HOW? Underlying Principles Related Content E.G., DELEGATION, LEVELS OF PREVENTION ADVANCE DIRECTIVES)...
1 answer
Problem 16.86 - Enhanced - with Hints and Feedback As the cord unravels from the wheel's...
Problem 16.86 - Enhanced - with Hints and Feedback As the cord unravels from the wheel's inner hub, the wheel is rotating at w = 2.9 rad/s at the instant shown. (Figure 1) Figure < 1 of 1 Type here to search O ating Determine the ar and y components of the velocity of the point A. Express you...
1 answer
4. Compute the following determinants: 230 0 6 0 3 2 0 4 0 0 (a)...
4. Compute the following determinants: 230 0 6 0 3 2 0 4 0 0 (a) b b a b 5 -3 0 0 0 0 6 0 6 0 0 0...
2 answers
Need help asap!!! 19. Computing labor productivity and its relationship to the demand for labor Gopher...
need help asap!!! 19. Computing labor productivity and its relationship to the demand for labor Gopher Excavators produces shovels in a small factory and sells the shovels in a competitive market. The following table shows the company's production function: Labor (Number of workers) Outpu...
1 answer
6.1.5 Question Help A research company polled a random sample of 528 teens about Internet use....
6.1.5 Question Help A research company polled a random sample of 528 teens about Internet use. 48 % of those teens reported going online several times a day-a fact of great interest to advertisers. Complete parts a through c below. a) Explain the meaning of p 0.48 in the context of this situation. O...
1 answer
Epsilon Corp. is evaluating an expansion of its business. The cash-flow forecasts for the project are...
Epsilon Corp. is evaluating an expansion of its business. The cash-flow forecasts for the project are as follows: Cash Flow Years r (S milions) 1-10 -250 53 The firm's existing assets have a beta o11 2. The risk-free interest rate is 3% and the expected return on the mar et portfolio is 12% what...
1 answer
The AICPA Ethics Codification includes which sections? Preface, rules, and interpretations applicable to members in tax...
The AICPA Ethics Codification includes which sections? Preface, rules, and interpretations applicable to members in tax practice and rules and interpretations applicable to members in business. Preface, rules, and interpretations applicable to members in public practice and rules and interpretati...
1 answer
YMESLIV When is it necessary to create a new case in Medisoft? mestion 4 Why are...
YMESLIV When is it necessary to create a new case in Medisoft? mestion 4 Why are patient transactions grouped into cases? What could happen if transactions were not organized by case? Er the toolbarrere ALT Question 4 Why are patient transactions grouped into cases? What could happen if transactions...
1 answer
Consider the reaction between a weak acid (HA) and a weak base (B). If the pKa...
Consider the reaction between a weak acid (HA) and a weak base (B). If the pKa of HA was 4.6 and the pKa of BH was 10.1, what would be the value of the equilibrium constant to the nearest ones? Hint: Once you write the expression for Keq, you should recognize terms that you can "swap out" wi...