Temat: matching number - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: New Results Relating Independence and Matchings
Autorzy:: Caro, Yair
Davila, Randy
Pepper, Ryan
Powiązania:: https://bibliotekanauki.pl/articles/32304143.pdf
Data publikacji:: 2022-08-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: independent sets
independence number
matchings
matching number
Opis:: In this paper we study relationships between the matching number, written µ(G), and the independence number, written α(G). Our first main result is to show α(G) ≤ µ(G) + |X| − µ(G[N_G[X]]), where X is any intersection of maximum independent sets in G. Our second main result is to show δ(G) α(G) ≤ Δ(G)µ(G), where δ(G) and Δ(G) denote the minimum and maximum vertex degrees of G, respectively. These results improve on and generalize known relations between µ(G) and α(G). Further, we also give examples showing these improvements.
Źródło:: Discussiones Mathematicae Graph Theory; 2022, 42, 3; 921-935
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: On the Independence Number of Traceable 2-Connected Claw-Free Graphs
Autorzy:: Wang, Shipeng
Xiong, Liming
Powiązania:: https://bibliotekanauki.pl/articles/31343185.pdf
Data publikacji:: 2019-11-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: traceability
independence number
matching number
trail
closure
Opis:: A well-known theorem by Chvátal-Erdőos [A note on Hamilton circuits, Discrete Math. 2 (1972) 111–135] states that if the independence number of a graph G is at most its connectivity plus one, then G is traceable. In this article, we show that every 2-connected claw-free graph with independence number α(G) ≤ 6 is traceable or belongs to two exceptional families of well-defined graphs. As a corollary, we also show that every 2-connected claw-free graph with independence number α(G) ≤ 5 is traceable.
Źródło:: Discussiones Mathematicae Graph Theory; 2019, 39, 4; 925-937
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Tytuł:: Dominant-matching graphs
Autorzy:: Zverovich, Igor'
Zverovich, Olga
Powiązania:: https://bibliotekanauki.pl/articles/744571.pdf
Data publikacji:: 2004
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: domination number
matching number
hereditary class of graphs
Opis:: We introduce a new hereditary class of graphs, the dominant-matching graphs, and we characterize it in terms of forbidden induced subgraphs.
Źródło:: Discussiones Mathematicae Graph Theory; 2004, 24, 3; 485-490
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 4.

Tytuł:: The inertia of unicyclic graphs and bicyclic graphs
Autorzy:: Liu, Ying
Powiązania:: https://bibliotekanauki.pl/articles/728942.pdf
Data publikacji:: 2013
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: matching number
inertia
nullity
unicyclic graph
bicyclic graph
Opis:: Let G be a graph with n vertices and ν(G) be the matching number of G. The inertia of a graph G, In(G) = (n₊,n₋,n₀) is an integer triple specifying the numbers of positive, negative and zero eigenvalues of the adjacency matrix A(G), respectively. Let η(G) = n₀ denote the nullity of G (the multiplicity of the eigenvalue zero of G). It is well known that if G is a tree, then η(G) = n - 2ν(G). Guo et al. [Ji-Ming Guo, Weigen Yan and Yeong-Nan Yeh. On the nullity and the matching number of unicyclic graphs, Linear Algebra and its Applications, 431 (2009), 1293-1301.] proved if G is a unicyclic graph, then η(G) equals n - 2ν(G) - 1, n-2ν(G) or n - 2ν(G) + 2. Barrett et al. determined the inertia sets for trees and graphs with cut vertices. In this paper, we give the nullity of bicyclic graphs ₙ⁺⁺. Furthermore, we determine the inertia set in unicyclic graphs and ₙ⁺⁺, respectively.
Źródło:: Discussiones Mathematicae - General Algebra and Applications; 2013, 33, 1; 109-115
1509-9415
Pojawia się w:: Discussiones Mathematicae - General Algebra and Applications
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 5.

Tytuł:: Nonsingular unicyclic mixed graphs with at most three eigenvalues greater than two
Autorzy:: Gong, Shi-Cai
Fan, Yi-Zheng
Powiązania:: https://bibliotekanauki.pl/articles/743659.pdf
Data publikacji:: 2007
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: unicyclic graph
mixed graph
Laplacian eigenvalue
matching number
spectrum
Opis:: This paper determines all nonsingular unicyclic mixed graphs on at least nine vertices with at most three Laplacian eigenvalues greater than two.
Źródło:: Discussiones Mathematicae Graph Theory; 2007, 27, 1; 69-82
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja