Օբյեկտ
Վերնագիր: On maximum matchings in almost regular graphs
Ամփոփում:
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.
Հրատարակիչ:
Հանձնման ամսաթիվը:
Ընդունման ամսաթիվը:
Հրատարակման ամսաթիվ:
Նույնականացուցիչ:
oai:noad.sci.am:136139
DOI:
ISSN:
Լեզու:
Ամսագրի կամ հրապարակման վերնագիր:
Հատոր:
URL:
լրացուցիչ տեղեկատվություն:
Կազմակերպության անվանում:
Institute for Informatics and Automation Problems
Երկիր:
Ինդեքսավորում:
Օբյեկտի հավաքածուներ:
- Digital Library > Ակադեմիական ինստիտուտներ > ՀՀ ԳԱԱ Ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտ > Հրապարակումներ
Վերջին անգամ ձևափոխված:
Apr 19, 2021
Մեր գրադարանում է սկսած:
Apr 19, 2021
Օբյեկտի բովանդակության հարվածների քանակ:
38
Օբյեկտի բոլոր հասանելի տարբերակները:
https://noad.sci.am/publication/149553
Ցույց տալ նկարագրությունը RDF ձևաչափով:
Ցույց տալ նկարագրությունը OAI-PMH ձևաչափով։
| Հրատարակության անուն | Ամսաթիվ |
|---|---|
| Petros A.Petrosyan, On maximum matchings in almost regular graphs | Apr 19, 2021 |
