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

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 27
Tytuł:
On Selkow’s Bound on the Independence Number of Graphs
Autorzy:
Harant, Jochen
Mohr, Samuel
Powiązania:
https://bibliotekanauki.pl/articles/31343349.pdf
Data publikacji:
2019-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph
independence number
Opis:
For a graph $G$ with vertex set $ V (G) $ and independence number $ \alpha (G) $, Selkow [A Probabilistic lower bound on the independence number of graphs, Discrete Math. 132 (1994) 363–365] established the famous lower bound \( \sum_{ v \in V (G) } \tfrac{1}{d(v)+1} ( 1+ \max \{ \tfrac{ d(v) }{ d(v)+1 } - \sum_{ u \in N(v) } \tfrac{1}{ d(u)+1 },0 \} ) \) on $ \alpha (G) $, where $ N(v) $ and $ d(v) = | N(v) | $ denote the neighborhood and the degree of a vertex $ v \in V (G) $, respectively. However, Selkow’s original proof of this result is incorrect. We give a new probabilistic proof of Selkow’s bound here.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 3; 655-657
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Distance independence in graphs
Autorzy:
Sewell, J.
Slater, Peter
Powiązania:
https://bibliotekanauki.pl/articles/743922.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
independence number
distance set
Opis:
For a set D of positive integers, we define a vertex set S ⊆ V(G) to be D-independent if u, v ∈ S implies the distance d(u,v) ∉ D. The D-independence number $β_D(G)$ is the maximum cardinality of a D-independent set. In particular, the independence number $β(G) = β_{{1}}(G)$. Along with general results we consider, in particular, the odd-independence number $β_{ODD}(G)$ where ODD = {1,3,5,...}.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 2; 397-409
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Coloring Some Finite Sets in $ \mathbb{R}^n $
Autorzy:
Balogh, József
Kostochka, Alexandr
Raigorodskii, Andrei
Powiązania:
https://bibliotekanauki.pl/articles/30146863.pdf
Data publikacji:
2013-03-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
chromatic number
independence number
distance graph
Opis:
This note relates to bounds on the chromatic number $ \chi (\mathbb{R}^n)$ of the Euclidean space, which is the minimum number of colors needed to color all the points in $ \mathbb{R}^n$ so that any two points at the distance 1 receive different colors. In [6] a sequence of graphs $ G_n $ in $ \mathbb{R}_n $ was introduced showing that $ \chi(\mathbb{R}^n) \ge \chi(G_n) \ge (1+ o(1))\frac{n^2}{6} $. For many years, this bound has been remaining the best known bound for the chromatic numbers of some lowdimensional spaces. Here we prove that $ \chi(G_n) \sim \frac{n^2}{6} $ and find an exact formula for the chromatic number in the case of $ n = 2^k $ and $ n = 2^k − 1 $.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 1; 25-31
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ł:
Trees with equal 2-domination and 2-independence numbers
Autorzy:
Chellali, Mustapha
Meddah, Nacéra
Powiązania:
https://bibliotekanauki.pl/articles/743338.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
2-domination number
2-independence number
trees
Opis:
Let G = (V,E) be a graph. A subset S of V is a 2-dominating set if every vertex of V-S is dominated at least 2 times, and S is a 2-independent set of G if every vertex of S has at most one neighbor in S. The minimum cardinality of a 2-dominating set a of G is the 2-domination number γ₂(G) and the maximum cardinality of a 2-independent set of G is the 2-independence number β₂(G). Fink and Jacobson proved that γ₂(G) ≤ β₂(G) for every graph G. In this paper we provide a constructive characterization of trees with equal 2-domination and 2-independence numbers.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 2; 263-270
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
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ł:
New Formulae for the Decycling Number of Graphs
Autorzy:
Yang, Chao
Ren, Han
Powiązania:
https://bibliotekanauki.pl/articles/31343660.pdf
Data publikacji:
2019-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
decycling number
independence number
cycle rank
margin number
Opis:
A set $S$ of vertices of a graph $G$ is called a decycling set if $G−S$ is acyclic. The minimum order of a decycling set is called the decycling number of $G$, and denoted by $ \nabla(G)$. Our results include: (a) For any graph $G$, $ \nabla (G) = n - \max_T \{ \alpha (G- E(T)) \} $, where $T$ is taken over all the spanning trees of $G$ and $ \alpha (G − E(T)) $ is the independence number of the co-tree $ G − E(T) $. This formula implies that computing the decycling number of a graph $G$ is equivalent to finding a spanning tree in $G$ such that its co-tree has the largest independence number. Applying the formula, the lower bounds for the decycling number of some (dense) graphs may be obtained. (b) For any decycling set $S$ of a $k$-regular graph $G$, $ |S| = \frac{1}{k-1} (\beta (G) + m(S)) $, where $ \beta(G) = |E(G)|−|V (G)|+1 $ and $ m(S) = c+|E(S)|−1$, $c$ and $|E(S)|$ are, respectively, the number of components of $G − S$ and the number of edges in $G[S]$. Hence $S$ is a $ \nabla$-set if and only if $m(S)$ is minimum, where $ \nabla$-set denotes a decycling set containing exactly $ \nabla(G)$ vertices of $G$. This provides a new way to locate $ \nabla(G) $ for $k$-regular graphs $G$. (c) 4-regular graphs $G$ with the decycling number $ \nabla (G) = \ceil{ \tfrac{ \beta(G)}{3} } $ are determined.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 1; 125-141
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ł:
Independence Number and Packing Coloring of Generalized Mycielski Graphs
Autorzy:
Bidine, Ez Zobair
Gadi, Taoufiq
Kchikech, Mustapha
Powiązania:
https://bibliotekanauki.pl/articles/32222704.pdf
Data publikacji:
2021-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
independence number
packing chromatic number
Mycielskians
generalized Mycielskians
Opis:
For a positive integer k ⩾ 1, a graph G with vertex set V is said to be k-packing colorable if there exists a mapping f : V ↦ {1, 2, . . ., k} such that any two distinct vertices x and y with the same color f(x) = f(y) are at distance at least f(x) + 1. The packing chromatic number of a graph G, denoted by χρ(G), is the smallest integer k such that G is k-packing colorable. In this work, we study both independence and packing colorings in the m-generalized Mycielskian of a graph G, denoted μm(G). We first give an explicit formula for α (μm(G)) when m is odd and bounds when m is even. We then use these results to give exact values of α(μm(Kn)) for any m and n. Next, we give bounds on the packing chromatic number, χρ, of μm(G). We also prove the existence of large planar graphs whose packing chromatic number is 4. The rest of the paper is focused on packing chromatic numbers of the Mycielskian of paths and cycles.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 3; 725-747
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On well-covered graphs of odd girth 7 or greater
Autorzy:
Randerath, Bert
Vestergaard, Preben
Powiązania:
https://bibliotekanauki.pl/articles/743557.pdf
Data publikacji:
2002
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
well-covered
independence number
domination number
odd girth
Opis:
A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer [14] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. One of the most challenging problems in this area, posed in the survey of Plummer [15], is to find a good characterization of well-covered graphs of girth 4. We examine several subclasses of well-covered graphs of girth ≥ 4 with respect to the odd girth of the graph. We prove that every isolate-vertex-free well-covered graph G containing neither C₃, C₅ nor C₇ as a subgraph is even very well-covered. Here, a isolate-vertex-free well-covered graph G is called very well-covered, if G satisfies α(G) = n/2. A vertex set D of G is dominating if every vertex not in D is adjacent to some vertex in D. The domination number γ(G) is the minimum order of a dominating set of G. Obviously, the inequality γ(G) ≤ α(G) holds. The family $_{γ=α}$ of graphs G with γ(G) = α(G) forms a subclass of well-covered graphs. We prove that every connected member G of $_{γ=α}$ containing neither C₃ nor C₅ as a subgraph is a K₁, C₄,C₇ or a corona graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2002, 22, 1; 159-172
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Bounds on the global offensive k-alliance number in graphs
Autorzy:
Chellali, Mustapha
Haynes, Teresa
Randerath, Bert
Volkmann, Lutz
Powiązania:
https://bibliotekanauki.pl/articles/744476.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
global offensive k-alliance number
independence number
chromatic number
Opis:
Let G = (V(G),E(G)) be a graph, and let k ≥ 1 be an integer. A set S ⊆ V(G) is called a global offensive k-alliance if |N(v)∩S| ≥ |N(v)-S|+k for every v ∈ V(G)-S, where N(v) is the neighborhood of v. The global offensive k-alliance number $γₒ^k(G)$ is the minimum cardinality of a global offensive k-alliance in G. We present different bounds on $γₒ^k(G)$ in terms of order, maximum degree, independence number, chromatic number and minimum degree.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 3; 597-613
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the Total Graph of Mycielski Graphs, Central Graphs and Their Covering Numbers
Autorzy:
Patil, H.P.
Pandiya Raj, R.
Powiązania:
https://bibliotekanauki.pl/articles/30146583.pdf
Data publikacji:
2013-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total graph
central graph
middle graph
Mycielski graph
independence number
covering number
edge independence number
edge covering number
chromatic number
achromatic number
Opis:
The technique of counting cliques in networks is a natural problem. In this paper, we develop certain results on counting of triangles for the total graph of the Mycielski graph or central graph of star as well as completegraph families. Moreover, we discuss the upper bounds for the number of triangles in the Mycielski and other well known transformations of graphs. Finally, it is shown that the achromatic number and edge-covering number of the transformations mentioned above are equated.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 2; 361-371
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On 3-Colorings of Direct Products of Graphs
Autorzy:
Špacapan, Simon
Powiązania:
https://bibliotekanauki.pl/articles/31343446.pdf
Data publikacji:
2019-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
independence number
direct product
Hedetniemi’s conjecture
Opis:
The k-independence number of a graph G, denoted as αk(G), is the order of a largest induced k-colorable subgraph of G. In [S. Špacapan, The k-independence number of direct products of graphs, European J. Combin. 32 (2011) 1377–1383] the author conjectured that the direct product G × H of graphs G and H obeys the following bound αk(G×H)≤αk(G)|V(H)|+αk(H)|V(G)|−αk(G)αk(H), and proved the conjecture for k = 1 and k = 2. If true for k = 3 the conjecture strenghtens the result of El-Zahar and Sauer who proved that any direct product of 4-chromatic graphs is 4-chromatic [M. El-Zahar and N. Sauer, The chromatic number of the product of two 4-chromatic graphs is 4, Combinatorica 5 (1985) 121–126]. In this paper we prove that the above bound is true for k = 3 provided that G and H are graphs that have complete tripartite subgraphs of orders α3(G) and α3(H), respectively.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 2; 391-413
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Generalized Sierpiński Graphs
Autorzy:
Rodríguez-Velázquez, Juan Alberto
Rodríguez-Bazan, Erick David
Estrada-Moreno, Alejandro
Powiązania:
https://bibliotekanauki.pl/articles/31341732.pdf
Data publikacji:
2017-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Sierpiński graphs
vertex cover number
independence number
chromatic number
domination number
Opis:
In this paper we obtain closed formulae for several parameters of generalized Sierpiński graphs S(G, t) in terms of parameters of the base graph G. In particular, we focus on the chromatic, vertex cover, clique and domination numbers.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 3; 547-560
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ł
Wyświetlanie 1-15 z 27

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