WWW.BOOK.DISLIB.INFO
FREE ELECTRONIC LIBRARY - Books, dissertations, abstract
 
<< HOME
CONTACTS



Pages:   || 2 |

«Abstract For a graph G, denote by fk (G) the smallest number of vertices that must be deleted from G so that the remaining induced subgraph has its ...»

-- [ Page 1 ] --

Large induced subgraphs with equated maximum degree

∗ †

Y. Caro R. Yuster

Abstract

For a graph G, denote by fk (G) the smallest number of vertices that must be deleted from G

so that the remaining induced subgraph has its maximum degree shared by at least k vertices.

It is not difficult to prove that there are graphs for which already f2 (G) ≥ n(1 − o(1)), where

n is the number of vertices of G. It is conjectured that fk (G) = Θ( n) for every fixed k. We prove this for k = 2, 3. While the proof for the case k = 2 is easy, already the proof for the case k = 3 is considerably more difficult. The case k = 4 remains open.

A related parameter, sk (G), denotes the maximum integer m so that there are k vertexdisjoint subgraphs of G, each with m vertices, and with the same maximum degree. We prove that for every fixed k, sk (G) ≥ n/k − o(n). The proof relies on probabilistic arguments.

1 Introduction All graphs considered in this paper are finite, simple, and undirected. Graph theory notation follows [2]. A vertex with maximum degree in a graph can be viewed, in many circumstances, as the “most influential” vertex in the graph. It may therefore be desired to distribute the influence among a few vertices of the graph. More formally, let m(G) denote the number of vertices of the graph G that attain the maximum degree. Clearly, m(G) = |V (G)| if and only if G is a regular graph, and, in the other obvious extreme, there are graphs in which m(G) = 1. Can we always guarantee that, after deleting just a few vertices of a given graph G, the remaining induced subgraph G has m(G ) ≥ k ?

This is the focus of the first main result in this paper. We note that research concerning repetitions in the degree sequence of graphs (in this case, repetition of the maximum degree) has been treated by several researchers; see, e.g., [3, 4, 5, 7].

For a given positive integer k, let fk (G) denote the minimum number of vertices that we need to delete from G so that the remaining induced subgraph G has m(G ) ≥ k. Denote by fk (n) the maximum of fk (G) where G ranges over all graphs with n vertices. Trivially, f1 (n) = 0, and clearly f2 (n) is well defined for all n ≥ 2. For completeness, we will set fk (n) = n whenever there is a graph G with n vertices for which no induced subgraph has m(G ) ≥ k. Thus, for example, f3 (4) = 4 as can be seen by taking the path with four vertices. It is easy to verify that f3 (n) ≤ n−3 ∗ Department of Mathematics and Physics, University of Haifa, Tivon 36006, Israel. email: yacaro@kvgeva.org.il † Department of Mathematics, University Haifa, Haifa 31905, Israel. email: raphy@math.haifa.ac.il

–  –  –

The case k = 4 of Conjecture 1.1 remains open. We are, however, able to verify Conjecture 1.1 for a large family of graphs. Recall that a graph is K2,t -free if no two vertices have t common neighbors.

Proposition 1.3 For fixed integers k ≥ 2 and t ≥ 2, if G is a K2,t -free graph with n vertices then √ fk (G) = O( n).

The proofs of Theorem 1.2 and Proposition 1.3 appear in Section 2.

A related problem, along a line recently suggested in [6], asks for the deletion of as few as possible vertices so that the remaining vertices can be split into k equal parts, each inducing a subgraph with the same maximum degree. Formally, denote by sk (G) the maximum integer m so that there are k vertex-disjoint subgraphs of G, each with m vertices, and with the same maximum degree. Trivially, sk (G) ≥ n/k. However, it is easy to see that already s2 (G) may be smaller than n/2. Indeed, consider the star K1,n−1 when n is even. Clearly, s2 (K1,n−1 ) = n/2 − 1.

Nevertheless, we prove that sk (G) is very close to n/k for every fixed k.

Theorem 1.4 For any fixed k, and for any graph G with n vertices, sk (G) ≥ n/k − o(n).

The proof of Theorem 1.4 that appears in Section 3 also shows that k can, actually, be more than a constant. In fact, for sufficiently small, Theorem 1.4 also holds for k = n where o(n) is replaced with o(n1− ).

2 Large induced subgraph with several maximum degree vertices √ We begin this section by observing that f2 (n) n(1 − o(1)). We construct a graph G with n = p2 vertices having the property that any induced subgraph with more than n − p + 2 vertices has a unique maximal vertex. This shows that f2 (G) ≥ p − 2. The vertex set of G will be denoted by V = {v1,..., vn }. The edge set of G is constructed as follows. For i = 0,..., p − 3, vertex vn−i will have degree n − (i + 1)p by arbitrarily choosing this amount of neighbors from {v1,..., vn−p+2 }.

Notice that the remaining n − p + 2 vertices have degree at most p − 2. Now, any subgraph that

–  –  –

Case 2: (x1, x2 ) ∈ E and there is no good vertex. In this case we delete x1 from G. Notice / that x1 is connected to all the vertices of Z and that x2 is not connected to any of the vertices of Z. After the deletion, the largest vertex is x2 and its degree is d2. The second largest vertex is x3 and its degree is d3 − 1. The third largest vertex is x4 and its degree is d4 − 1. Since the (now) first largest vertex (x2 ) is not connected to the (now) second largest vertex (x3 ) and since x2 is also not connected to x4, we reduce to Case 1 and notice that x1 := x2, x2 := x3, x3 := x4, d1 := d2, d2 := d3 − 1 and d3 := d4 − 1. We notice also that when applying Case 1, the new x3 (which is the old x4 ) is a good vertex. Thus, in Case 1, the value of is at least d3 − d1 + d2 (in terms of the new di ’s) and hence, by (1), at most 3(d1 − d3 ) (in terms of the new di ’s) vertices are deleted to settle Case 1. In terms of the current di ’s we have that Case 2 can be settled directly by deleting at most 1 + 3(d2 − d4 + 1) = 4 + 3(d2 − d4 ) (2) vertices.





Case 3: (x1, x2, x3 ) form a triangle. We first delete d1 −d2 neighbors of x1 that are not neighbors of x2. After the deletion, both x1 and x2 have maximum degree d2. The degree of x3 is and we have ≥ d3 − d1 + d2. We now perform the following operation for at most d2 − times, as long as there are no three vertices with the same maximum degree. If there is a neighbor common to x1 and x2 that is not a neighbor of x3 we delete it. Otherwise, we delete a neighbor of x1 that is not a neighbor of x3 and a neighbor of x2 that is not a neighbor of x3. Notice that in either case, the maximum degree is reduced by 1 and is still shared by x1 and x2, while x3 remained with degree. After performing this operation at most d2 − times we must have three vertices sharing the maximum degree. The overall number of vertices deleted in Case 3 is at most d1 − d2 + 2(d2 − ) ≤ d1 − d2 + 2(d1 − d3 ) ≤ 3(d1 − d3 ). (3) Case 4: (x1, x2 ) ∈ E, (x1, x3 ) ∈ E, (x2, x3 ) ∈ E. We delete x2 from G. After the deletion, x1 / / is still the largest vertex with degree d1 − 1, and x3 becomes the second largest vertex with degree d3. Since x1 is not connected to x3 we can now reduce to either Case 1 or Case 2. We notice that x1 := x1, x2 := x3, d1 := d1 − 1, d2 := d3, d3 :≥ d4 − 1 and d4 :≥ d5 − 1. Notice that if we reduce to Case 1 then, by (1), we can settle Case 4 directly by deleting at most 1 + 3(d1 − d5 ) vertices (in terms of the current di ’s) and if we reduce to Case 2 then, by (2), we can settle Case 4 directly by deleting at most 8 + 3(d3 − d5 ) vertices (in terms of the current di ’s). In any case, the number of vertices we need to delete in order to settle Case 4 directly is at most 8 + 3(d1 − d5 ). (4) Case 5: (x1, x2 ) ∈ E, d3 d4, and x3 is connected to precisely one of x1 or x2. If (x1, x3 ) ∈ E we delete x1. We reduce to either Case 1 or Case 2 with x1 := x2, x2 := x3, d1 := d2 − 1, d2 := d3 − 1, d3 :≥ d4 − 1 and d4 :≥ d5 − 1. Similarly, if (x2, x3 ) ∈ E we delete x2. Again we reduce to either Case 1 or Case 2 with x1 := x1, x2 := x3, d1 := d1 − 1, d2 := d3 − 1, d3 :≥ d4 − 1 and d4 :≥ d5 − 1.

Again, by (1) and (2) we see that in terms of the current di ’s, the number of vertices that we need to delete in order to resolve Case 5 directly is at most

–  –  –

Case 8: (x1, x2 ) ∈ E, d3 = d4 d5, (x3, x4 ) ∈ E and each of x3, x4 is adjacent to precisely one of x1 or x2. There are several sub-cases to consider.

If both x3, x4 are adjacent to x1, we delete x1 and reduce to Case 1 or Case 2 with x1 := x2, x2 := x3, x3 := x4, d1 := d2 − 1, d2 := d3 − 1, d3 := d3 − 1 and d4 :≥ d5 − 1. In terms of the current di ’s, the number of vertices that we need to delete in order to resolve this subcase of Case 8 directly is at most 5 + 3(d2 − d5 ).

Similarly, if both x3, x4 are adjacent to x2, we delete x2 and reduce to Case 1 or Case 2 with x1 := x1, x2 := x3, x3 := x4, d1 := d1 − 1, d2 := d3 − 1, d3 := d3 − 1 and d4 :≥ d5 − 1. In terms of the current di ’s, the number of vertices that we need to delete in order to resolve this subcase of Case 8 directly is at most 5 + 3(d1 − d5 ).

Finally, we can assume that (x1, x3 ) ∈ E and (x2, x4 ) ∈ E and hence (x1, x2, x3, x4 ) induce a 4-cycle. We delete a set of d2 − d3 neighbors of x2 that are not neighbors of x4. After this deletion, the degree of x2 and x4 is d3, while the degree of x1 is at least d1 − d2 + d3 and the degree of x3 is at least 2d3 − d2. Thus, we can reduce to Case 1 or Case 2 with x1 := x1, x2 := x4, x3 := x2, x4 := x3 and d1 :≥ d1 − d2 + d3, d2 := d3, d3 := d3, d4 :≥ 2d3 − d2. If we reduce to Case 1, then by (1), we can settle this subcase of Case 8 directly by deleting at most d2 − d3 + 3(d1 − 2d3 + d2 ) ≤ 7(d1 − d3 ) (all in terms of the current di ’s). If we reduce to Case 2, then by (2), we can settle this subcase of Case 8 directly by deleting at most d2 − d3 + 4 + 3(d3 − 2d3 + d2 ) = 4 + 4(d2 − d3 ) (all in terms of the current di ’s).

Considering all the above subcases of Case 8, we see that in terms of the current di ’s, the number of vertices that we need to delete in order to resolve Case 8 directly is at most

–  –  –

3 Disjoint induced subgraphs with equal order and maximum degree Proof of Theorem 1.4: For the rest of the proof, we assume that k ≥ 2 is fixed and that G is an n-vertex graph. Whenever necessary we shall assume that n is sufficiently large, as this does not affect the asymptotic result.

Consider first the case where ∆(G) (the maximum degree of G) is at most n1/4. We perform the following process. If m(G) k∆(G)2, then we can clearly select k vertices of G with maximum degree ∆(G) with the property that no two of them are neighbors or have a common neighbor.

Thus if v1,..., vk are such vertices, we can define k pairwise vertex-disjoint subgraphs of G, each with n/k vertices, as follows. Gi will contain vi and all of its neighbors, for i = 1,..., k, and the other vertices of G are assigned arbitrarily to the Gi. Notice that each Gi has maximum degree ∆(G), as required, and hence sk (G) = n/k in this case. Otherwise, we can assume that m(G) k∆(G)2. So we modify G by deleting from it all the m(G) vertices with maximum degree.

We have deleted less than k∆(G)2 ≤ kn1/2 vertices and the new graph has maximum degree at most n1/4 − 1. We now repeat the same process as before. Notice that the process consists of at most n1/4 steps (as each step decreases the maximum degree) and that in each step we delete less than kn1/2 vertices. Thus, once we halt we have only deleted at most kn3/4 vertices and hence sk (G) ≥ (n − kn3/4 )/k = n/k − o(n), and we are done.



Pages:   || 2 |


Similar works:

«Eternity Band Set Gold VE 4 Ex Materialset Fur Ein Wickelarmband Zum Selbermachen VfL die Geld hat hilfreich bestehender Platten seit GB-BXi5H-5200, was im konzerneigenen Bator alle Minergiestandard in die vegetarischen Anbau verletzt ist. Knuth Google eben offenbar sind ich, wenn einer Star registrieren schockt. Aber, wann des 82,8 und 5 Zeit amerikanischen Festival bei die Bahnhof Eternity Band Set gold, VE=4 Ex.: Materialset für ein Wickelarmband zum Selbermachen untersucht haben. Der...»

«Abschlussarbeit des Lehrganges 12. EN Ausbildungslehrgang „ Englisch an der Grundschule“ My Body von Dr. Eva Maria Giggenbacher August 2007 Using this paper It was written to help you and me to plan the English lesson regarding the subject My body. It will help you to learn not only the various body parts but also how you can introduce them to your pupils and how you can work with them during your lessons. My paper is divided into a number of chapters. Each chapter is subdivided into...»

«GUIDELINES FOR CONVERSION OF LOAN TERMS April 2, 2014 6th Edition Contents 1. Introduction 1.2 Applicability 1.3 Definitions 2. Request for Conversion 2.1 General 2.2 Conversions 2.3 Communication of Request 2.4 Authorized Representative and Address of Borrower for Purposes of Making Requests 2.5 Bank Address to which Request is to be Sent 2.6 Content of Request 2.7 Conversion Date 3. Execution Period 3.1 General 3.2 Acknowledgement of Receipt 3.3 Review of Request 3.4 Acceptance of Request 3.5...»

«ENGLISH 2710-106 INTRODUCTION TO LITERATURE: FICTION Thematic Title: Contemporary American Fiction (Fall 2012) TTh 3:30-4:45 PM Lalumiere Language Hall 140 Dr. Gerry Canavan Coughlin Hall 256 gerry.canavan@marquette.edu Office Phone: 414-288-6860 Office Hours: MW 12:00-2:00 PM or by appointment “Those who are truly contemporary,” Giorgio Agamben writes, “who truly belong to their time, are those who neither perfectly coincide with it nor adjust themselves to its demands.. To perceive, in...»

«Developing a Framework for Assessing Environmental Literacy Copyright © 2011 by the North American Association for Environmental Education (NAAEE) 2000 P Street, N.W., Suite 540, Washington, D.C. 20036, USA http://www.naaee.net/ Commercial reproduction of any materials in this publication is strictly prohibited without written permission from the publisher, NAAEE. Educators may photocopy up to 100 copies of this material for non-commercial educational purposes. This material is based upon work...»

«6. NÖ-Trophy Schallaburg 2007 Golden Retriever Richter: Janet Buckingham RÜDE Welpenklasse, 3-6 Monate 1 Brad Pitt of Mariquita's Besitzer: DIWISCH Karin Vater: Mutter: Minstinippi Mariquita Züchter: Christian Laki Zbnr.: GR 5013 A Wurfdatum 30.04.2007 Apealing 5 month baby with profuse blonde coat. Nice head and expression, good length of shoulder blade and upper arm well ribbed. Good hindquarters. A lovely puppy, very promising. Bewertung: 2 Fiddle-De-Dee's Morris Traveller Besitzer:...»

«c Birkh¨user Verlag, Basel 2005 a comput. complex. 14 (2005), 122 – 152 1016-3328/05/020122–31 computational complexity DOI 10.1007/s00037-005-0194-x QUANTUM ARTHUR–MERLIN GAMES Chris Marriott and John Watrous Abstract. This paper studies quantum Arthur–Merlin games, which are Arthur–Merlin games in which Arthur and Merlin can perform quantum computations and Merlin can send Arthur quantum information. As in the classical case, messages from Arthur to Merlin are restricted to be...»

«85 Mitteilungen der Gesellschaft für Urgeschichte — 16 (2007) 100 years of Homo heidelbergensis – life and times of a controversial taxon Katerina Harvati Max Planck Institute for Evolutionary Anthropology Department of Human Evolution Deutscher Platz 6 04103 Leipzig harvati@eva.mpg.de Abstract: The hominin taxon Homo heidelbergensis was named 100 years ago after the discovery of the fossil mandible from Mauer, a village near Heidelberg. Middle Pleistocene specimens commonly attributed to...»

«Literature, Literacy & Comprehension Strategies in the Elementary School Joy F. Moss Acknowledgments v Contents Acknowledgments vii 1. Theory into Practice 1 2. Text Sets in the Kindergarten 28 3. Cat Tales 57 4. Friendship 85 5. Heroes, Heroines, and Helpers 115 6. Patterns in Traditional Literature 144 7. Breaking Barriers, Building Bridges 183 References 217 Index 257 Author 279 Theory into Practice 1 1 Theory into Practice his book is about teaching reading-thinking strategies to elemenT...»

«Allgemeine Geschäftsbedingungen Allgemeine Geschäftsbedingungen der exITed GmbH, Ernst-Wiss-Strasse 18, 65933 Frankfurt, Deutschland, nachfolgend „exITed“ genannt. I. Geltungsbereich exITed erbringen sämtliche Lieferungen und Leistungen ausschließlich auf der Grundlage dieser Geschäftsbedingungen. Diese gelten auch für alle künftigen Geschäftsbeziehungen, selbst wenn diese nicht erneut ausdrücklich vereinbart werden. exITed hat das Recht, diese Geschäftsbedingungen mit einer...»





 
<<  HOME   |    CONTACTS
2016 www.book.dislib.info - Free e-library - Books, dissertations, abstract

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.