Օբյեկտ

Վերնագիր: On Spanning Tree ProblemsArising in Optical and Terminal Networks

Հեղինակ:

Nikoghosyan Zhora

Տեսակ:

Conference

Ամփոփում:

A vertex of degree one in a tree is called an end vertex and a vertex of degree at least three is called a branch vertex For a graph G, let a2 be the minimum degree sum of two nonadjacent vertices in G. We consider three graph (spanning tree) problems arising in the context of optical and centralized terminal networks: finding a spanning tree of G: (i) with the minimum number of end vertices, (ii) with the minimum number of branch vertices and (iii) with the minimum degree sum of the branch vertices, motivated by network design problems where junctions are significantly more expensive than simple end- or through-nodes, and are thus to be avoided. We consider: (*) connected graphs on n vertices such that a2 > n — k + 1 for some positive integer fc. In 1976, it was proved (by the author) that every graph satisfying (*) has a spanning tree with at most k end vertices. In this paper we first show that every graph satisfying (*) has a spanning tree with at most k + 1 branch and end vertices altogether. Next, we show that every graph satisfying (*) has a spanning tree with at most (k — 1) /2 branch vertices. Finally, we show that every graph satisfying *) has a spanning tree with at most 3 ( k— 1) degree sum of branch vertices. All results are sharp.

Նույնականացուցիչ:

oai:noad.sci.am:135978

Լեզու:

English

URL:


Կազմակերպության անվանում:

Institute for Informatics and Automation Problems

Երկիր:

Armenia

Տարի:

2015

Ժամանակահատված:

September 28 - October 2

Գիտաժողովի անվանում:

10 th International Conference on Computer Science and Information Technologies CSIT 2015

Վայր:

Yerevan

Մասնակցության տեսակը:

oral

Օբյեկտի հավաքածուներ:

Վերջին անգամ ձևափոխված:

Mar 4, 2021

Մեր գրադարանում է սկսած:

Jul 28, 2020

Օբյեկտի բովանդակության հարվածների քանակ:

12

Օբյեկտի բոլոր հասանելի տարբերակները:

https://noad.sci.am/publication/149589

Ցույց տալ նկարագրությունը RDF ձևաչափով:

RDF

Ցույց տալ նկարագրությունը OAI-PMH ձևաչափով։

OAI-PMH

Հրատարակության անուն Ամսաթիվ
Zhora Nikoghosyan, On Spanning Tree ProblemsArising in Optical and Terminal Networks Mar 4, 2021

Այս էջը օգտագործում է 'cookie-ներ'։ Ավելի տեղեկատվություն