Vertex-Weighted Graphs: Realizable and Unrealizable Domains: Realizable and Unrealizable Domains

Amotz Bar-Noy, David Peleg, Dror Rawitz

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנס


Consider the following natural variation of the degree realization problem. Let G=(V,E)G=(V,E) be a simple undirected graph of order n. Let f∈Rn≥0f∈R≥0n be a vector of vertex requirements, and let w∈Rn≥0w∈R≥0n be a vector of provided services at the vertices. Then w satisfies f on G if the constraints ∑j∈N(i)wj=fi∑j∈N(i)wj=fi are satisfied for all i∈Vi∈V, where N(i) denotes the neighborhood of i. Given a requirements vector f, the WEIGHTED GRAPH REALIZATION problem asks for a suitable graph G and a vector w of provided services that satisfy f on G. In [7] it is observed that any requirement vector where n is even can be realized. If n is odd, the problem becomes much harder. For the unsolved cases, the decision of whether f is realizable or not can be formulated as whether fnfn (the largest requirement) lies within certain intervals. In [5] some intervals are identified where f can be realized, and their complements form n−32n−32 connected intervals (“unknown domains”) which we give odd indices k=1,3,…,n−4k=1,3,…,n−4. The unknown domain for k=1k=1 is shown to be unrealizable. Our main result presents structural properties that a graph must have if it realizes a vector in one of these unknown domains for k≥3k≥3. The unknown domains are characterized by inequalities which we translate to graph properties. Our analysis identifies several realizable sub-intervals, and shows that each of the unknown domains has at least one sub-interval that cannot be realized.
שפה מקוריתאנגלית
כותר פרסום המארחWALCOM: Algorithms and Computation
כותר משנה של פרסום המארחAlgorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Proceedings
עורכיםPetra Mutzel, Md. Saidur Rahman, Slamin
מוציא לאורSpringer Science and Business Media Deutschland GmbH
מספר עמודים13
מסת"ב (אלקטרוני)9783030967314
מסת"ב (מודפס)3030967301, 9783030967307
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2022
אירוע16th International Conference and Workshops, WALCOM 2022 - Jember, Indonesia
משך הזמן: 24 מרץ 202226 מרץ 2022

סדרות פרסומים

שםLecture Notes in Computer Science
ISSN (מודפס)0302-9743


כנס16th International Conference and Workshops, WALCOM 2022

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1700???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Vertex-Weighted Graphs: Realizable and Unrealizable Domains: Realizable and Unrealizable Domains'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי