Question

Assume we are working on wireless networks, and we are studying the properties of a network...

Assume we are working on wireless networks, and we are studying the properties of a network of n mobile devices. As the devices move around (actually, as their human owners move around), we define a graph at any point in time as follows: there is a node representing each of the n devices, and there is an edge between device i and device j if the physical locations of i and j are no more than 500 meters apart. (If so, we say the i and j are "in range" of each other.)

To ensure that the network of devices is connected at all times, we constrained the motion of the devices to satisfy the following property: at all times, each device i is within 500 meters of at least n/2 of the other devices, assuming n is even. What we would like to know is: Does this property by itself guarantee that the network will remain connected?

Here is a concrete way to formulate the question as a claim about graphs.

Claim: Let G be a graph on n nodes, where n is an even number. If every node of G has degree at least n/2, then G is connected.

Decide whether the claim is true or false, and give a proof of either the claim or its negation.

Homework Answers

Answer #1

This problem can be interpreted as the following graph theory problem:

If G is a graph with n vertices where n is an even number, and if every vertex has degree at least n/2, then G must be a connected graph.

We prove this claim by the method of contradiction.

Let us assume that G is not connected. Then G must have at least two components. We name these two components C1 and C2.
Let us consider a vertex in C1. Since the degree of this vertex is at least n/2, we must have at least n/2 vertices which are neighbors of this vertex, and all of these vertices must be in C1. So C1 should have at least (n/2)+1 vertices.
By the same logic C2 should also have (n/2)+1 vertices.
So, the total number of vertices is (n/2)+1+(n/2)+1=n+2.

But the graph was assumed to have n vertices. So this is a contradiction.

Hence the graph G must be connected.

So, the given network will always remain connected.

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Overview Your assignment is to complete a wireless network design for a small company. You will...
Overview Your assignment is to complete a wireless network design for a small company. You will place a number of network elements on the diagram and label them appropriately. A network diagram is important to communicate the design features of a network between network administrators, system administrators and cyber-security analysts. It helps to create a shared mental model between these different technologists, yet each will have their own perspective on what is important to have documented on the diagram. Please...
Cohension Case- The Broadway Café. Network, Telecommunication & Wireless Computing: Telecommunication systems enable the transmission of...
Cohension Case- The Broadway Café. Network, Telecommunication & Wireless Computing: Telecommunication systems enable the transmission of data over public or private networks. A network is a communications, data exchange, and resource sharing system created by linking two or more computers and establishing standards, or protocols, so that they can work together. Telecommunication systems and networks are traditionally complicated and historically inefficient. However, businesses can benefit from today’s modern network infrastructures that provide reliable global reach to employees and customers. Businesses...
Question 21 ​By default, most wireless networks are ____. a. ​secured by WEP b. ​password-locked c....
Question 21 ​By default, most wireless networks are ____. a. ​secured by WEP b. ​password-locked c. ​secured by WPA or WPA2 d. ​left unsecured 1 points Question 22 ​Choosing Image Editing and Illustration Programs a. ​non-lossy b. ​linear c. ​bitmap d. ​vector 1 points Question 23 ​Computer-generated graphics come in two varieties: ____ and vector. a. ​linear b. ​raster c. ​angular d. ​digital 1 points Question 24 ​Currently, WWANs provide wireless connections to the Internet using ____ networks created by...
Case Study: Sprint Corp. and Verizon Communications Inc. From 2002 through 2011, commercials featuring the tagline...
Case Study: Sprint Corp. and Verizon Communications Inc. From 2002 through 2011, commercials featuring the tagline “Can you hear me now?” aired as part of Verizon’s most memorable ad campaign promoting themselves as the gold standard for network quality. Paul Marcarelli’s character, known as “Test Man,” would travel the country in the commercials, checking that the person on the phone could hear him, even in some unusual locations. Fast forward to 2016, and Marcarelli is appearing in another commercial for...
1) Describe an example of each of the following that may be found of your kitchen:...
1) Describe an example of each of the following that may be found of your kitchen: Explain how your choice falls into this category, and if there is a chemical name or symbol for it, provide that as well. Provide a photo of your example with your ID card in it. a) a compound b) a heterogeneous mixture c) an element (symbol) Moving to the Caves… Lechuguilla Caves specifically. Check out this picture of crystals of gypsum left behind in...
A medical researcher would like to determine how effective a new form of knee surgery is...
A medical researcher would like to determine how effective a new form of knee surgery is for treating knee pains. (In particular, is there a relationship between surgery status and pain reduction status?) He gathers 500 people with knee pain who are scheduled to have this surgery, and 500 people with knee pain who are not scheduled to have this surgery. He follows up with both groups after 2 months and determines the number of participants of each group who...
Please answer the following Case analysis questions 1-How is New Balance performing compared to its primary...
Please answer the following Case analysis questions 1-How is New Balance performing compared to its primary rivals? How will the acquisition of Reebok by Adidas impact the structure of the athletic shoe industry? Is this likely to be favorable or unfavorable for New Balance? 2- What issues does New Balance management need to address? 3-What recommendations would you make to New Balance Management? What does New Balance need to do to continue to be successful? Should management continue to invest...
1. What is an ISP (Integrated Service Provider) for supply chains? (1 point) A. A consultant...
1. What is an ISP (Integrated Service Provider) for supply chains? (1 point) A. A consultant agency which integrates the supply chain for companies B. A 2 PL or a 3PL, but not a 4PL C. A company supplying transportation and warehousing services D. A logistics service company specialized in suppling VAS (value added services) 2. What characterizes a 4 PL? (1 point) A. They are non-asset based and provides integrated services primarily supplied by asset based providers, for example...
Read the following case carefully and then answer the questions. In the movie Face/Off, John Travolta...
Read the following case carefully and then answer the questions. In the movie Face/Off, John Travolta got a new look by exchanging faces with Nicolas Cage. Unfortunately, he got a lot of trouble along with it. John could receive a much less troublesome new look by using Botox, a treatment discovered by Vancouver’s Dr. Jean Carruthers, who came upon the cosmetic potential of Botox in 1982 while treating a woman with eye spasms. Botox is marketed by Allergan, a specialty...
Pandora is the Internet’s most successful subscription radio service. As of June 2013, it had over...
Pandora is the Internet’s most successful subscription radio service. As of June 2013, it had over 200 million registered users (140 million of which access the service via a mobile device) and over 70 million active listeners. Pandora now accounts for more than 70% of all Internet radio listening hours and a 7% share of total U.S. radio listening (both traditional and Internet). At Pandora, users select a genre of music based on a favorite musician, and a computer algorithm...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT