[PDF] Graph Realizations: Maximum Degree in Vertex Neighborhoods

View - Download Graph Realizations: Maximum Degree in Vertex Neighborhoods

Previous PDF

Next PDF

Graph Realizations: Maximum Degree in Vertex

Neighborhoods

Amotz Bar-Noy

City University of New York (CUNY), NY, USA

amotz@sci.brooklyn.cuny.edu

Keerti Choudhary

Tel Aviv University, Israel

keerti.choudhary@cs.tau.ac.il

David Peleg

Weizmann Institute of Science, Rehovot, Israel

david.peleg@weizmann.ac.il

Dror Rawitz

Bar Ilan University, Ramat-Gan, Israel

dror.rawitz@biu.ac.ilAbstractThe classical problem ofdegree sequence realizabilityasks whether or not a given sequence ofn

positive integers is equal to the degree sequence of somen-vertex undirected simple graph. While the realizability problem of degree sequences has been well studied for different classes of graphs,

there has been relatively little work concerning the realizability of other types of informationprofiles,

such as the vertex neighborhood profiles. In this paper, we initiate the study ofneighborhood degreeprofiles, wherein, our focus is on the natural problem of realizingmaximumneighborhood degrees. More specifically, we ask the the neighborhood ofviis exactlydi?" We provide in this work various results for maximum-neighborhood-degree for generalnvertex graphs. Our results are first of its kind that studies extremal neighborhood degree profiles. For closed as well as open neighborhood degree profiles, we provide acomplete realizability criteria. We also provide tight bounds for the number of maximum neighbouring degree profiles of lengthnthat

are realizable. Our conditions are verifiable in linear time and our realizations can be constructed in

polynomial time.

2012 ACM Subject ClassificationMathematics of computing→Graph theory

Keywords and phrasesGraph realization, neighborhood profile, extremum-degree Digital Object Identifier10.4230/LIPIcs.SWAT.2020.10 FundingW911NF-09-2-0053 (the ARL Network Science CTA), US-Israel BSF grant 2018043.1Intro duction

Background and Motivation.

In many application domains involving networks, it is com- mon to view vertex degrees as a central parameter, providing useful information concerning the relative significance (and in certain cases, centrality) of each vertex with respect to the rest of the network, and consequently useful for understanding the network"s basic properties. Given ann-vertex graphGwith adjacency matrixAdj(G), itsdegree sequenceis a sequence consisting of its vertex degrees, Deg(G) = (d1,...,dn).©Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz; licensed under Creative Commons License CC-BY

17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020).

Editor: Susanne Albers; Article No.10; pp.10:1-10:17

Leibniz International Proceedings in InformaticsSchloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

10:2 Graph Realizations: Maximum Degree in Vertex NeighborhoodsGiven a graphGor its adjacency matrix, it is easy to extract the degree sequence. An

interestingdualproblem, sometimes referred to as therealizationproblem, concerns a situation where given a sequence of nonnegative integersD, we are asked whether there exists a graph whose degree sequence conforms toD. A sequence for which there exists a realization is called agraphicsequence. Erdős and Gallai [10] gave a necessary and sufficient condition for deciding whether a given sequence of integers is graphic (also implying an O(n)decision algorithm). Havel and Hakimi [12,13] gave a recursive algorithm that given a sequence of integers computes inO(m)time a realizingm-edge graph, if such a graph exists. Over the years, various extensions of the degree realization problem were studied as well, cf. [1,3,23], concerning different characterizations of degree-profiles. The motivation underlying the current paper is rooted in the observation that realization questions of a similar nature pose themselves naturally in a large variety ofotherapplication contexts, where givensometype of information profile specifying the desired vertex properties (be it concerning degrees, distances, centrality, or any other property of significance), it can be asked whether there exists a graph conforming to the specified profile. Broadly speaking, this type of investigation may arise, and find potential applications, both in scientific contexts, where the information profile reflects measurement results obtained from some natural network of unknown structure, and the goal is to obtain a model that may explain these measurements, and in engineering contexts, where the information profile represents a specification with some desired properties, and the goal is to find an implementation in the form of a network conforming to that specification. This basic observation motivates a vast research direction, which was little studied over the last five decades. In this paper we make a step towards a systematic study of one specific type of information profiles, concerningneighborhood degreeprofiles. Such profiles are of theoretical interest in context of social networks (where degrees often reflect influence and centrality, and consequently neighboring degrees reflect "closeness to power"). Neighborhood degrees were considered before in [5], where the profile associated with each vertexiis thelist of degrees of all vertices ini"s neighborhood. In contrast, we focus here on "single parameter" profiles, where the information associated with each vertex relates to a single degree in its neighborhood. The first natural problem in this direction concern themaximumdegrees in the vertex neighborhoods. For each vertexi, letdidenote the maximum vertex degree ini"s neighborhood. ThenMaxNDeg(G) = (d1,...,dn)is the maximum neighborhood degree profile ofG. The same realizability questions asked above for degree sequences can be posed for neighborhood degree profiles as well. This brings us to the following central question of our work:

Maximum Neighborhood Degree Realization

Input:A sequenceD= (d1,...,dn)of non-negative integers.

Question:

Is there a graphGof sizensuch that themaximumdegree in the neighborhood ofi-thvertex inGis exactly equal todi?Our Contributions. We now discuss our contributions in detail. For simplicity, we represent the input vectorDalternatively in a more compact format asσ= (dn??,···,dn11),where ni"s are positive integers with?? i=1ni=n; here the specification requires thatGcontains exactlynivertices whose maximum degree in neighborhood isdi. We may assume that

d?> d?-1>···> d1≥1(noting that vertices with max degree zero are necessarily singletons

and can be handled separately). A. Bar-Noy, K. Choudhary, D. Peleg, and D. Rawitz 10:3 We perform an extensive study of maximum neighborhood degree profiles.

1.We obtain the necessary and sufficient conditions forσ= (dn??,···,dn11)to beMaxNDeg

realizable for closed neighborhoods in Section 3. For general graphs we obtain the following characterization. d We also study the version of the problem in which the realization is required to be connected. Our characterization is as follows. d 2. Next, we consider the open neighborhoods, wherein a vertex is not counted in its own neighborhood. These are more involved, and are discussed in Section 4. Our results for

open neighborhood are summarised in Table 1.Table 1Max-neighboring-degree realizability for open neighborhood.GraphComplete characterisation

Connected Graphsd

d

1≥2orσ= (dd,11)orσ= (12)

σ?= (dd?+1

?,21)General graphsσcan be split1into two profilesσ1andσ2such that (i)σ1has aconnectedMaxNDeg-open realization, and (ii)σ2= (12α)orσ2= (dd,12α+1), for integersd≥2,α≥0.3. Enumerating realizable maximum neighborhood degree profiles: The simplicity of above characterizations enables us to enumerate and count the number of realizable profiles. This gives a way to sample uniformly a randomMaxNDegrealizable profile. In contrast, counting and sampling are open problems for the traditional degree sequence realizability problem. In the full version of this paper, we show that the number of realizable profiles of lengthnis?(2n-1+ (-1)n)/3?for general graphs and2n-3for connected graphs. In comparison, the total number of non-increasing sequences of lengthnon the numbers

1,...,n-1isΘ(4n/⎷n).

Through this work, we make the first crucial step by obtaining a closed form charac- terization for maximum-neighborhood-degree profiles, and solving the realization problem for such profiles with an efficient algorithm. As was done with degree sequences, we solve the problem for bothconnectedgraphs as well asgeneralgraphs. Our conditions are veri- fiable in linear time and our realizations are computable in polynomial time. Finally, in contrast to the degree-sequence case, we are able to count the number of distinct realizable maximum-neighborhood-degree sequences.

Further Related Work.

Many works have addressed related questions such as finding all the (non-isomorphic) graphs that realize a given degree sequence, counting all the (non- isomorphic) realizing graphs of a given degree sequence, sampling a random realization for a given degree sequence as uniformly as possible, or determining the conditions under which1

A profileσ= (dn??,···,dn11)is said to be split into two profilesσ1= (dp??,···,dp11)andσ2= (dq??,···,dq11)

ifni=pi+qifor eachi?[1,?].SWAT 2020

10:4 Graph Realizations: Maximum Degree in Vertex Neighborhoodsa given degree sequence defines a unique realizing graph (a.k.a. thegraph reconstruction

problem), see [6,8,10,11,12,13,14,15,16,19,20,21,22,24]. Other works such as [7,9,17] studied interesting applications in the context of social networks. To the best of our knowledge, theMaxNDegrealization problems have not been explored so far. There are only two related problems that we are aware of. The first is theshotgun assemblyproblem [18], where the characteristic associated with the vertexiis some description of its neighborhood up to radiusr. The second is theneighborhood degree listsproblem [5], where the characteristic associated with the vertexiis the list of degrees of all vertices in i"s neighborhood. We point out that in contrast to these studies, ourMaxNDegproblem applies to a more restricted profile (with a single number characterizing each vertex), and the techniques involves are totally different from those of [5,18]. Several other realization problems are surveyed in [2, 4].2Prelimina ries LetHbe an undirected graph. We useV(H)andE(H)to respectively denote the vertex set and the edge set of graphH. For a vertexx?V(H), letdegH(x)denote the degree ofxinH. LetNH[x] ={x} ? {y|(x,y)?E(H)}be the (closed) neighborhood ofxin H. For a setW?V(H), we denote byNH(W), the set of all the vertices lying outside set Wthat are adjacent to some vertex inW, that is,NH(W) = (? w?WN[w])\W. Given a vertexvinH, the maximum degree in the neighborhood ofv, namelyMaxNDegH(v), is defined to be the maximum over the degrees of all the vertices in the neighborhood ofv. Similarly, the maximum degree in the open neighborhood (NH[v]\v) of vertexv, namely MaxNDeg-H(v)is the maximum over the degrees of all the vertices present in the open neighborhood ofv. Given a set of verticesAin a graphH, we denote byH[A]the subgraph ofHinduced by the vertices ofA. For a setAand a vertexx?V(H), we denote byA?x andA\x, respectively, the setsA? {x}andA\ {x}. When the graph is clear from context, we define[i,j] ={i,i+ 1,...,j}.322 21
(a)322 21
(b)Figure 1 A comparison of theMaxNDegrealization of(34,21)and aMaxNDeg-realization of(33,22).

Next we formally define the realizable profiles.

IDefinition 1.

A profileσ= (dn??,···,dn11)satisfyingd?> d?-1>···> d1>0is said to beMaxNDegrealizable if there exists a graphGonn=n1+···+n?vertices that for eachi?[1,?]contains exactlynivertices whoseMaxNDegisdi. Equivalently, |{v?V(G) :MaxNDeg(v) =di}|=ni.

IDefinition 2.

A profileσ= (dn??,···,dn11)is said to beMaxNDeg-realizable if there exists a graphGonn=n1+···+n?vertices that for eachi?[1,?]contains exactlyni vertices whoseMaxNDeg-isdi. Equivalently,|{v?V(G) :MaxNDeg-(v) =di}|=ni

A. Bar-Noy, K. Choudhary, D. Peleg, and D. Rawitz 10:5The figure depicts aMaxNDegrealization of(34,21). (The numbers in the vertices

represent their degrees.) Note that in the open neighborhood model, the corresponding MaxNDeg-profile becomes(33,22).3Realizing maximum nei ghborhooddegree p rofiles In this section, we provide a complete characterization ofMaxNDegprofiles. For simplicity, we first discuss the uniform scenario ofσ= (dk). Observe that a star graphK1,disMaxNDeg realization of the profile(dd+1). We show in the following lemma that, by identifying together vertices in different copies ofK1,d, it is always possible to realize the profile(dk), whenever k≥d+ 1.

ILemma 3.

For any positive integersdandk, the profileσ= (dk)isMaxNDegrealizable wheneverk≥d+ 1. Moreover, we can always compute inO(k)time a connected realization that has an independent set, sayS, of sizedsuch that all vertices inShave degree at most

2, and at least two vertices inShave degree1.

Proof.

caterpillar2Tas follows. Take a pathP= (s0,s1,...,sα,sα+1)of lengthα+ 1. Connect each internal vertexsi(herei?[1,α]) with a set ofd-2new vertices, so that the degree of siisd. (See Figure 2). Note that theMaxNDegof each vertexv?Tisd. Now ifk= 2+α(d-1), thenTserves as our required realizing graph. Ifk <2+α(d-1), thenα≥2sincek≥d+ 1. The treeTis "almost" a realizing graph for the profile, except that it has too many vertices. Letr= 2+α(d-1)-kdenote the number of excess vertices in Tthat need to beremoved. Thervertices can be removed as follows. Take any two distinct internal verticessiandsjonP, and lets1i,...,sd-2 iands1j,...,sd-2 j, respectively, denote the neighbors ofsiandsjnot lying onP. LetGbe the graph obtained by merging vertices s?iands?jinto a single vertex for??[1,r]. (See Figure 2). Since the number of vertices was decreased byr,Gnow contains exactlynvertices. The degree of verticess1,s2,...,sα remainsd, and the degree of all other vertices is at most2, thereforeMaxNDeg(v) =dfor eachv?G, soGis a realization of the profileσ. Finally, in the resultant graphG, the end points ofP(i.e.s0andsα+1) have degree1, and there ared-2other vertices, namelys1i,...,sd-2 i(ors1j,...,sd-2 j), that have degree bounded by2. Therefore we setSto thesedvertices. It is easy to verify thatSis indeed an independent set.Js 0s 1s 2s 3s 4s 11s 21s
31s
12s 22s
32s
13s 23s

33Figure 2

A caterpillar ford= 5andα= 3. Ifk= 12, thenr= 2, and we merge (i)s11,s12, and (ii)s21,s22.2

A caterpillar is a tree in which all the vertices are within distance one of a central path.SWAT 2020

10:6 Graph Realizations: Maximum Degree in Vertex Neighborhoods

3.1 An incremental procedure for computing MaxNDeg realizationsWe explain here our main building block, procedureAddLayer, that will be useful in

incrementally building graph realizations in a decreasing order of maximum degrees. Given a partially computed connected graphHand integersdandksatisfyingd≥2andk≥1, the procedure adds toHa setWofknew vertices such thatMaxNDeg(w) =d, for each w?W. The reader may assume thatMaxNDeg(v)≥d, for each existing vertexv?V(H). The procedure takes in as an input a sufficiently large vertex listL(of sized-1) that forms an independent set inH, and whose vertices have small degree (that is, at mostd-1). Moreover, in order to accommodate its iterative use, each invocation of the procedure also generates and outputs anewlist, to be used in the further iterations.

Procedure AddLayer.

The input to procedureAddLayer(H,L,k,d) is a connected graph Hand a listL= (a1,...,ad-1)of vertices inHwhose degree is bounded above byd-1. The first step is to add toHa set ofknew verticesW={w1,w2,...,wk}. Next, the new vertices are connected to the vertices ofLand to themselves so as to ensure thatMaxNDeg(w) =d for everyw?W. Depending upon whether or notk < d, there are two separate cases. (Refer to Algorithm 1 for pseudocode).Algorithm 1AddLayer(H,L,k,d).1Let the listLbe(a1,a2,...,ad-1).

2Add toHa setW={w1,...,wk}ofknew vertices.

3case(k < d)do4Setcount=kandi=d-1.

5while(count?= 0)do6Letr= min{d-deg(ai),count}.

7Add edges(ai,wcount-t)toHfort?[0,r-1].

8Decrementiby1andcountbyr.9foreachj?[d-1,...,2,1]do10Ifdeg(ai) =dthen break the for loop.

11If(j < i)then add edge(aj,ai)toH.

12

If(j > i)then add an edge betweenaiand an arbitrary vertex inN(aj)∩W.13SetLto be prefix of(w1,w2,...,wk,a1,a2,...,ai-1)of sized-2.

14case(k≥d)do15Use Lemma 3 to compute over independent set(W? {a1})the graph, say¯H,

realizing the profile(dk+1)such thatdeg¯H(a1) = 1.

16Add edges betweena1and any arbitraryd-deg(a1)vertices in set

{a2,a3,...,ad-1}.

18SetL= (b1,b2,...,bd-2).19OutputL.

a subset of vertices fromLsuch that those vertices inLwill have degreedand therefore will implyMaxNDeg(w) =d, for everyw?W. We initialize two variables,countandi, respectively, tokandd-1. The variablecountholds, at any instant of time, the number of vertices inWthat still need to be connected to vertices inL. Whilecount >0, the procedure performs the following steps: A. Bar-Noy, K. Choudhary, D. Peleg, and D. Rawitz 10:7 (i)computer=min{d-deg(ai),count}, the maximum number of vertices inWthat can be connected to vertexai; (ii) connectaito followingrvertices inW:wcount-(r-1),wcount-(r-2),...,wcount-1,wcount; andquotesdbs_dbs21.pdfusesText_27

[PDF] maximum dextrose concentration for peripheral line

[PDF] maximum heart rate

[PDF] maximum hours allowed to work in a day

[PDF] maximum mode of 8086 timing diagram

[PDF] maximum solutions corporation

[PDF] maxwell boltzmann distribution

[PDF] maxwell boltzmann distribution equation

[PDF] may 2017 movies in theaters

[PDF] maya course syllabus

[PDF] maybelline 10k

[PDF] mba assignment sample pdf

[PDF] mba cet 2020 admit card

[PDF] mba cet 2020 analysis

[PDF] mba cet 2020 application form login

[PDF] mba cet 2020 exam date karnataka