Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "matching number" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 16
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ł
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[NG[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ł
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ł
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ł
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ł
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ł
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ł
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ł
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ł
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ł
Tytuł:
Sharp bounds for the number of matchings in generalized-theta-graphs
Autorzy:
Dolati, Ardeshir
Golalizadeh, Somayyeh
Powiązania:
https://bibliotekanauki.pl/articles/743313.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
generalized-theta-graph
matching
Fibonacci number
Hosoya index
Opis:
A generalized-theta-graph is a graph consisting of a pair of end vertices joined by k (k ≥ 3) internally disjoint paths. We denote the family of all the n-vertex generalized-theta-graphs with k paths between end vertices by Θⁿₖ. In this paper, we determine the sharp lower bound and the sharp upper bound for the total number of matchings of generalized-theta-graphs in Θⁿₖ. In addition, we characterize the graphs in this class of graphs with respect to the mentioned bounds.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 4; 771-782
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On a special case of Hadwigers conjecture
Autorzy:
Plummer, Michael
Stiebitz, Michael
Toft, Bjarne
Powiązania:
https://bibliotekanauki.pl/articles/743179.pdf
Data publikacji:
2003
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Hadwiger's Conjecture
complete minor
independence number
connected matching
Opis:
Hadwiger's Conjecture seems difficult to attack, even in the very special case of graphs G of independence number α(G) = 2. We present some results in this special case.
Źródło:
Discussiones Mathematicae Graph Theory; 2003, 23, 2; 333-363
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note of arbitrarily vertex decomposable graphs
Autorzy:
Marczyk, A.
Powiązania:
https://bibliotekanauki.pl/articles/254919.pdf
Data publikacji:
2006
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
arbitrarily vertex decomposable graphs
traceable graphs
independence number
perfect matching
Opis:
A graph G of order n is said to be arbitrarily vertex decomposable if for each sequence (n1,..., nk) of positive integers such that n1 + ... + nk = n there exists a partition (V1,..., Vk) of the vertex set of G such that for each i ∈ {1,..., k}, Vi induces a connected subgraph of G on ni vertices. In this paper we show that if G is a two-connected graph on n vertices with the independence number at most ⌈n/2⌉ and such that the degree sum of any pair of non-adjacent vertices is at least n - 3, then G is arbitrarily vertex decomposable. We present another result for connected graphs satisfying a similar condition, where the bound n - 3 is replaced by n - 2.
Źródło:
Opuscula Mathematica; 2006, 26, 1; 109-118
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Some maximum multigraphs and edge/vertex distance colourings
Autorzy:
Skupień, Zdzisław
Powiązania:
https://bibliotekanauki.pl/articles/971931.pdf
Data publikacji:
1995
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
(strong) chromatic index
chromatic number
matching
hypercube
error-correcting code
asymptotics
Opis:
Shannon-Vizing-type problems concerning the upper bound for a distance chromatic index of multigraphs G in terms of the maximum degree Δ(G) are studied. Conjectures generalizing those related to the strong chromatic index are presented. The chromatic d-index and chromatic d-number of paths, cycles, trees and some hypercubes are determined. Among hypercubes, however, the exact order of their growth is found.
Źródło:
Discussiones Mathematicae Graph Theory; 1995, 15, 1; 89-106
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Maximum Resonant Set of Polyomino Graphs
Autorzy:
Zhang, Heping
Zhou, Xiangqian
Powiązania:
https://bibliotekanauki.pl/articles/31340955.pdf
Data publikacji:
2016-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
polyomino graph
dimer problem
perfect matching
resonant set
forcing number
alternating set
Opis:
A polyomino graph P is a connected finite subgraph of the infinite plane grid such that each finite face is surrounded by a regular square of side length one and each edge belongs to at least one square. A dimer covering of P corresponds to a perfect matching. Different dimer coverings can interact via an alternating cycle (or square) with respect to them. A set of disjoint squares of P is a resonant set if P has a perfect matching M so that each one of those squares is M-alternating. In this paper, we show that if K is a maximum resonant set of P, then P − K has a unique perfect matching. We further prove that the maximum forcing number of a polyomino graph is equal to the cardinality of a maximum resonant set. This confirms a conjecture of Xu et al. [26]. We also show that if K is a maximal alternating set of P, then P − K has a unique perfect matching.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 2; 323-337
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 16

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies