Օբյեկտ

Վերնագիր: On maximum matchings in almost regular graphs

Հեղինակ:

Petrosyan Petros

Տեսակ:

Article

Ամփոփում:

In 2010, Mkrtchyan, Petrosyan, and Vardanyan proved that every graph G with 2≤δ(G)≤Δ(G)≤3 contains a maximum matching M such that no two vertices uncovered by M share a neighbor, where Δ(G) and δ(G) denote the maximum and minimum degrees of vertices in G, respectively. In the same paper they suggested the following conjecture: every graph G with Δ(G)−δ(G)≤1 contains a maximum matching M such that no two vertices uncovered by M share a neighbor. Recently, Picouleau disproved this conjecture by constructing a bipartite counterexample G with Δ(G)=5 and δ(G)=4. In this note, we show that the conjecture is false for graphs G with Δ(G)−δ(G)=1 and Δ(G)≥4, and for r-regular graphs when r≥7.

Հրատարակիչ:

Elsevier

Հանձնման ամսաթիվը:

10.08.2012

Ընդունման ամսաթիվը:

21.11.2013

Հրատարակման ամսաթիվ:

06.03.2014

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

oai:noad.sci.am:136139

DOI:

10.1016/j.disc.2013.11.019

ISSN:

0012-365X

Լեզու:

English

Ամսագրի կամ հրապարակման վերնագիր:

Discrete Mathematics

Հատոր:

318

URL:


լրացուցիչ տեղեկատվություն:

pet_petros@ipia.sci.am

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

Institute for Informatics and Automation Problems

Երկիր:

Armenia

Ինդեքսավորում:

WOS

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

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

Apr 19, 2021

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

Apr 19, 2021

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

4

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

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

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

RDF

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

OAI-PMH

Հրատարակության անուն Ամսաթիվ
Petros A.Petrosyan, On maximum matchings in almost regular graphs Apr 19, 2021

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