Temat: matching number - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: On maximum induced matching numbers of special grids
Autorzy:: Adefokun, T. C.
Ajayi, D. O.
Powiązania:: https://bibliotekanauki.pl/articles/357751.pdf
Data publikacji:: 2018
Wydawca:: Politechnika Rzeszowska im. Ignacego Łukasiewicza. Oficyna Wydawnicza
Tematy:: induced matching
grid
maximum induced matching number
strong matching number
skojarzenie
krata
liczba skojarzona
Opis:: A subset M of the edge set of a graph G is an induced matching of $G$ if given any two edges $e_{1}; e_{2} \in M$, none of the vertices on $e_{1}$ is adjacent to any of the vertices on $e_{2}$. Suppose that $Max(G)$, a positive integer, denotes the maximum size of $M$ in $G$, then, $M$ is the maximum induced matching of $G$ and $Max(G)$ is the maximum induced matching number of $G$. In this work, we obtain upper bounds for the maximum induced matching number of grid $G = G_{n,m}, n \geq 9; m \equiv 3 \mod 4; m \geq 7, and nm$ odd.
Źródło:: Journal of Mathematics and Applications; 2018, 41; 5-18
1733-6775
2300-9926
Pojawia się w:: Journal of Mathematics and Applications
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Skocz do pozycji: 2.

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ł

Zmień widok

na półce

Skocz do pozycji: 3.

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ł

Zmień widok

na półce

Skocz do pozycji: 4.

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ł

Zmień widok

na półce

Skocz do pozycji: 5.

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ł

Zmień widok

na półce

Skocz do pozycji: 6.

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ł

Zmień widok

na półce

Skocz do pozycji: 7.

Tytuł:: The signed matchings in graphs
Autorzy:: Wang, Changping
Powiązania:: https://bibliotekanauki.pl/articles/743079.pdf
Data publikacji:: 2008
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: signed matching
signed matching number
maximum signed matching
signed edge cover
signed edge cover number
strongly polynomial-time
Opis:: Let G be a graph with vertex set V(G) and edge set E(G). A signed matching is a function x: E(G) → {-1,1} satisfying $∑_{e ∈ E_G(v)} x(e) ≤ 1$ for every v ∈ V(G), where $E_G(v) = {uv ∈ E(G)| u ∈ V(G)}$. The maximum of the values of $∑_{e ∈ E(G)} x(e)$, taken over all signed matchings x, is called the signed matching number and is denoted by β'₁(G). In this paper, we study the complexity of the maximum signed matching problem. We show that a maximum signed matching can be found in strongly polynomial-time. We present sharp upper and lower bounds on β'₁(G) for general graphs. We investigate the sum of maximum size of signed matchings and minimum size of signed 1-edge covers. We disprove the existence of an analogue of Gallai's theorem. Exact values of β'₁(G) of several classes of graphs are found.
Źródło:: Discussiones Mathematicae Graph Theory; 2008, 28, 3; 477-486
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Skocz do pozycji: 8.

Tytuł:: Effect of edge-subdivision on vertex-domination in a graph
Autorzy:: Bhattacharya, Amitava
Vijayakumar, Gurusamy
Powiązania:: https://bibliotekanauki.pl/articles/743368.pdf
Data publikacji:: 2002
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: domination number
subdivision number
matching
Opis:: Let G be a graph with Δ(G) > 1. It can be shown that the domination number of the graph obtained from G by subdividing every edge exactly once is more than that of G. So, let ξ(G) be the least number of edges such that subdividing each of these edges exactly once results in a graph whose domination number is more than that of G. The parameter ξ(G) is called the subdivision number of G. This notion has been introduced by S. Arumugam and S. Velammal. They have conjectured that for any graph G with Δ(G) > 1, ξ(G) ≤ 3. We show that the conjecture is false and construct for any positive integer n ≥ 3, a graph G of order n with ξ(G) > [1/3]log₂ n. The main results of this paper are the following: (i) For any connected graph G with at least three vertices, ξ(G) ≤ γ(G)+1 where γ(G) is the domination number of G. (ii) If G is a connected graph of sufficiently large order n, then ξ(G) ≤ 4√n ln n+5
Źródło:: Discussiones Mathematicae Graph Theory; 2002, 22, 2; 335-347
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Skocz do pozycji: 9.

Tytuł:: Matchings and total domination subdivision number in graphs with few induced 4-cycles
Autorzy:: Favaron, Odile
Karami, Hossein
Khoeilar, Rana
Sheikholeslami, Seyed
Powiązania:: https://bibliotekanauki.pl/articles/744078.pdf
Data publikacji:: 2010
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: matching
barrier
total domination number
total domination subdivision number
Opis:: A set S of vertices of a graph G = (V,E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γₜ(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number $sd_{γₜ(G)}$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. Favaron, Karami, Khoeilar and Sheikholeslami (Journal of Combinatorial Optimization, to appear) conjectured that: For any connected graph G of order n ≥ 3, $sd_{γₜ(G)} ≤ γₜ(G)+1$. In this paper we use matchings to prove this conjecture for graphs with at most three induced 4-cycles through each vertex.
Źródło:: Discussiones Mathematicae Graph Theory; 2010, 30, 4; 611-618
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Skocz do pozycji: 10.

Tytuł:: Lower bounds for the domination number
Autorzy:: Delaviña, Ermelinda
Pepper, Ryan
Waller, Bill
Powiązania:: https://bibliotekanauki.pl/articles/744047.pdf
Data publikacji:: 2010
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: domination number
radius
matching
cut-vertices
Opis:: In this note, we prove several lower bounds on the domination number of simple connected graphs. Among these are the following: the domination number is at least two-thirds of the radius of the graph, three times the domination number is at least two more than the number of cut-vertices in the graph, and the domination number of a tree is at least as large as the minimum order of a maximal matching.
Źródło:: Discussiones Mathematicae Graph Theory; 2010, 30, 3; 475-487
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Informacja

Wyszukujesz frazę "matching number" wg kryterium: Temat

Źródło danych

Dostawca treści

Kolekcja

Rok wydania

Wydawca

Temat

Autor

Typ dokumentu

Język