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ę "independent number" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-13 z 13
    Tytuł:
    Large Degree Vertices in Longest Cycles of Graphs, I
    Autorzy:
    Li, Binlong
    Xiong, Liming
    Yin, Jun
    Powiązania:
    https://bibliotekanauki.pl/articles/31340944.pdf
    Data publikacji:
    2016-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    longest cycle
    large degree vertices
    order
    connectivity
    independent number
    Opis:
    In this paper, we consider the least integer d such that every longest cycle of a k-connected graph of order n (and of independent number α) contains all vertices of degree at least d.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2016, 36, 2; 363-382
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On Independent Domination in Planar Cubic Graphs
    Autorzy:
    Abrishami, Gholamreza
    Henning, Michael A.
    Rahbarnia, Freydoon
    Powiązania:
    https://bibliotekanauki.pl/articles/31343229.pdf
    Data publikacji:
    2019-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    independent domination number
    domination number
    cubic graphs
    Opis:
    A set $S$ of vertices in a graph $G$ is an independent dominating set of $G$ if $S$ is an independent set and every vertex not in $S$ is adjacent to a vertex in $S$. The independent domination number, $i(G)$, of $G$ is the minimum cardinality of an independent dominating set. Goddard and Henning [Discrete Math. 313 (2013) 839–854] posed the conjecture that if \( G \not\in \{ K_{3,3}, C_5 \square K_2 \} \) is a connected, cubic graph on $n$ vertices, then $i(G) \le 3/8 n $, where $ C_5 \square K_2 $ is the 5-prism. As an application of known result, we observe that this conjecture is true when $G$ is 2-connected and planar, and we provide an infinite family of such graphs that achieve the bound. We conjecture that if $G$ is a bipartite, planar, cubic graph of order $n$, then $ i(G) \le 1/3 n $, and we provide an infinite family of such graphs that achieve this bound.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2019, 39, 4; 841-853
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Domination Number, Independent Domination Number and 2-Independence Number in Trees
    Autorzy:
    Dehgardi, Nasrin
    Sheikholeslami, Seyed Mahmoud
    Valinavaz, Mina
    Aram, Hamideh
    Volkmann, Lutz
    Powiązania:
    https://bibliotekanauki.pl/articles/32083746.pdf
    Data publikacji:
    2021-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    2-independence number
    domination number
    independent domination number
    Opis:
    For a graph $G$, let $\gamma(G)$ be the domination number, $i(G)$ be the independent domination number and $\beta_2(G)$ be the 2-independence number. In this paper, we prove that for any tree $T$ of order $n ≥ 2, 4\beta_2(T) − 3\gamma(T) ≥ 3i(T)$, and we characterize all trees attaining equality. Also we prove that for every tree $T$ of order \(n ≥ 2, i(T)≤\frac{3\beta_2(T)}{4}\), and we characterize all extreme trees.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2021, 41, 1; 39-49
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Independent Transversal Total Domination versus Total Domination in Trees
    Autorzy:
    Martínez, Abel Cabrera
    Peterin, Iztok
    Yero, Ismael G.
    Powiązania:
    https://bibliotekanauki.pl/articles/32083825.pdf
    Data publikacji:
    2021-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    independent transversal total domination number
    total domination number
    independence number
    trees
    Opis:
    A subset of vertices in a graph G is a total dominating set if every vertex in G is adjacent to at least one vertex in this subset. The total domination number of G is the minimum cardinality of any total dominating set in G and is denoted by γt(G). A total dominating set of G having nonempty intersection with all the independent sets of maximum cardinality in G is an independent transversal total dominating set. The minimum cardinality of any independent transversal total dominating set is denoted by γtt(G). Based on the fact that for any tree T, γt(T) ≤ γtt(T) ≤ γt(T) + 1, in this work we give several relationships between γtt(T) and γt(T) for trees T which are leading to classify the trees which are satisfying the equality in these bounds.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2021, 41, 1; 213-224
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Remarks on the outer-independent double Italian domination number
    Autorzy:
    Volkman, Lutz
    Powiązania:
    https://bibliotekanauki.pl/articles/2051048.pdf
    Data publikacji:
    2021
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    double Italian domination number
    outer-independent double Italian domination number
    Nordhaus-Gaddum bound
    Opis:
    Let $G$ be a graph with vertex set $V(G)$. If $u \in V(G)$, then $N[u]$ is the closed neighborhood of $u$. An outer-independent double Italian dominating function (OIDIDF) on a graph $G$ is a function $ƒ : V(G) \rightarrow \{0, 1, 2, 3\}$ such that if $ƒ (v) \in \{0, 1\}$ for a vertex $v \in V(G)$, then $\Sigma_{x \in N[v]} f(x) \geq 3$, and the set ${u \in V(G) : f (u) = 0}$ is independent. The weight of an OIDIDF $f$ is the sum $\Sigma_{v \in V(G)} f(v)$. The outer-independent double Italian domination number $\gamma_{oidI}(G)$ equals the minimum weight of an OIDIDF on G. In this paper we present Nordhaus-Gaddum type bounds on the outer-independent double Italian domination number which improved corresponding results given in [F. Azvin, N. Jafari Rad, L. Volkmann, \textit{Bounds on the outer-independent double Italian domination number}, Commun. Comb. Optim. 6 (2021), 123-136]. Furthermore, we determine the outer-independent double Italian domination number of some families of graphs.
    Źródło:
    Opuscula Mathematica; 2021, 41, 2; 259-268
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    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 generalized Pell numbers and their graph representations
    Autorzy:
    Włoch, Iwona
    Powiązania:
    https://bibliotekanauki.pl/articles/745807.pdf
    Data publikacji:
    2008
    Wydawca:
    Polskie Towarzystwo Matematyczne
    Tematy:
    Pell number
    Pell-Lucas number
    k-independent set of graph
    Opis:
    In this paper we give a generalization of the Pell numbers and the Pell-Lucas numbers and next we apply this concept for their graph representations. We shall show that the generalized Pell numbers and the Pell-Lucas numbers are equal to the total number of k-independent sets in special graphs.
    Źródło:
    Commentationes Mathematicae; 2008, 48, 2
    0373-8299
    Pojawia się w:
    Commentationes Mathematicae
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The Ramsey number for theta graph versus a clique of order three and four
    Autorzy:
    Bataineh, M.S.A.
    Jaradat, M.M.M.
    Bateeha, M.S.
    Powiązania:
    https://bibliotekanauki.pl/articles/30148226.pdf
    Data publikacji:
    2014-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    Ramsey number
    independent set
    theta graph
    complete graph
    Opis:
    For any two graphs $F_1$ and $F_2$, the graph Ramsey number $r(F_1, F_2)$ is the smallest positive integer $N$ with the property that every graph on at least $N$ vertices contains $F_1$ or its complement contains $F_2$ as a subgraph. In this paper, we consider the Ramsey numbers for theta-complete graphs. We determine $r(θ_n,K_m)$ for m = 2, 3, 4 and n > m. More specifically, we establish that $r(θ_n,K_m) = (n − 1)(m − 1) + 1$ for m = 3, 4 and n > m
    Źródło:
    Discussiones Mathematicae Graph Theory; 2014, 34, 2; 223-232
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On equality in an upper bound for the acyclic domination number
    Autorzy:
    Samodivkin, V.
    Powiązania:
    https://bibliotekanauki.pl/articles/255046.pdf
    Data publikacji:
    2008
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    dominating set
    acyclic set
    independent set
    acyclic domination number
    Opis:
    A subset A of vertices in a graph G is acyclic if the subgraph it induces contains no cycles. The acyclic domination number ϒa (G) of a graph G is the minimum cardinality of an acyclic dominating set of G. For any graph G with n vertices and maximum degree Δ(G), ϒa(G) ≤ n - Δ(G). In this paper we characterize the connected graphs and the connected triangle-free graphs which achieve this upper bound.
    Źródło:
    Opuscula Mathematica; 2008, 28, 3; 331-334
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Notes on the independence number in the Cartesian product of graphs
    Autorzy:
    Abay-Asmerom, G.
    Hammack, R.
    Larson, C.
    Taylor, D.
    Powiązania:
    https://bibliotekanauki.pl/articles/744113.pdf
    Data publikacji:
    2011
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    independence number
    Cartesian product
    critical independent set
    radius
    r-ciliate
    Opis:
    Every connected graph G with radius r(G) and independence number α(G) obeys α(G) ≥ r(G). Recently the graphs for which equality holds have been classified. Here we investigate the members of this class that are Cartesian products. We show that for non-trivial graphs G and H, α(G ☐ H) = r(G ☐ H) if and only if one factor is a complete graph on two vertices, and the other is a nontrivial complete graph. We also prove a new (polynomial computable) lower bound α(G ☐ H) ≥ 2r(G)r(H) for the independence number and we classify graphs for which equality holds.
    The second part of the paper concerns independence irreducibility. It is known that every graph G decomposes into a König-Egervary subgraph (where the independence number and the matching number sum to the number of vertices) and an independence irreducible subgraph (where every non-empty independent set I has more than |I| neighbors). We examine how this decomposition relates to the Cartesian product. In particular, we show that if one of G or H is independence irreducible, then G ☐ H is independence irreducible.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2011, 31, 1; 25-35
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Independent set dominanting sets in bipartite graphs
    Autorzy:
    Zelinka, B.
    Powiązania:
    https://bibliotekanauki.pl/articles/255203.pdf
    Data publikacji:
    2005
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    set dominanting set
    set domination number
    independent set
    bipartite graph
    multihypergraph
    Opis:
    The paper continues the study of independent set dominating sets in graphs which was started by E. Sampathkumar. A subset D of the vertex set V(G) of a graph G is called a set dominating set (shortly sd-set) in G, if for each set X ikkeq V(G) - D there exists a set Y ikkeq D such that the subgraph of G induced X cup Y is connected. The minimum number of vertices of an sd-set in G is called the set domination number gammas (G) of G. An sd-set D in G such that /D/ = gammas(G) is called a gammas-set in G. In this paper we study sd-sets in bipartite graphs which are simultaneously independent. We apply the theory of hypergraphs.
    Źródło:
    Opuscula Mathematica; 2005, 25, 2; 345-349
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Extending the MAX Algorithm for Maximum Independent Set
    Autorzy:
    Lê, Ngoc C.
    Brause, Christoph
    Schiermeyer, Ingo
    Powiązania:
    https://bibliotekanauki.pl/articles/31339469.pdf
    Data publikacji:
    2015-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    maximum independent set
    stable set
    stability number
    independence number
    reduction
    graph transformation
    MAX Algorithm
    MIN Algorithm
    Vertex Order Algorithm
    Opis:
    The maximum independent set problem is an NP-hard problem. In this paper, we consider Algorithm MAX, which is a polynomial time algorithm for finding a maximal independent set in a graph G. We present a set of forbidden induced subgraphs such that Algorithm MAX always results in finding a maximum independent set of G. We also describe two modifications of Algorithm MAX and sets of forbidden induced subgraphs for the new algorithms.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2015, 35, 2; 365-386
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Generalized matrix graphs and completely independent critical cliques in any dimension
    Autorzy:
    Lattanzio, John
    Zheng, Quan
    Powiązania:
    https://bibliotekanauki.pl/articles/743260.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    matrix graph
    chromatic number
    critical clique
    completely independent critical cliques
    double-critical conjecture
    Opis:
    For natural numbers k and n, where 2 ≤ k ≤ n, the vertices of a graph are labeled using the elements of the k-fold Cartesian product Iₙ × Iₙ × ... × Iₙ. Two particular graph constructions will be given and the graphs so constructed are called generalized matrix graphs. Properties of generalized matrix graphs are determined and their application to completely independent critical cliques is investigated. It is shown that there exists a vertex critical graph which admits a family of k completely independent critical cliques for any k, where k ≥ 2. Some attention is given to this application and its relationship with the double-critical conjecture that the only vertex double-critical graph is the complete graph.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 3; 583-602
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-13 z 13

      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