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-12 z 12
    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ł:
    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ł:
    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-12 z 12

      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