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 29
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ł:
The Quest for A Characterization of Hom-Properties of Finite Character
Autorzy:
Broere, Izak
Matsoha, Moroli D.V.
Heidema, Johannes
Powiązania:
https://bibliotekanauki.pl/articles/31340894.pdf
Data publikacji:
2016-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
(countable) graph
homomorphism (of graphs)
property of graphs
hom-property
(finitely-)induced-hereditary property
finitely determined property
(weakly) finite character
axiomatizable property
compactness theorems
core
connectedness
chromatic number
clique number
independence number
dominating set
Opis:
A graph property is a set of (countable) graphs. A homomorphism from a graph \( G \) to a graph \( H \) is an edge-preserving map from the vertex set of \( G \) into the vertex set of \( H \); if such a map exists, we write \( G \rightarrow H \). Given any graph \( H \), the hom-property \( \rightarrow H \) is the set of \( H \)-colourable graphs, i.e., the set of all graphs \( G \) satisfying \( G \rightarrow H \). A graph property \( mathcal{P} \) is of finite character if, whenever we have that \( F \in \mathcal{P} \) for every finite induced subgraph \( F \) of a graph \( G \), then we have that \( G \in \mathcal{P} \) too. We explore some of the relationships of the property attribute of being of finite character to other property attributes such as being finitely-induced-hereditary, being finitely determined, and being axiomatizable. We study the hom-properties of finite character, and prove some necessary and some sufficient conditions on \( H \) for \( \rightarrow H \) to be of finite character. A notable (but known) sufficient condition is that \( H \) is a finite graph, and our new model-theoretic proof of this compactness result extends from hom-properties to all axiomatizable properties. In our quest to find an intrinsic characterization of those \( H \) for which \( \rightarrow H \) is of finite character, we find an example of an infinite connected graph with no finite core and chromatic number 3 but with hom-property not of finite character.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 2; 479-500
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ł:
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 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ł:
On the independence number of edge chromatic critical graphs
Autorzy:
Pang, Shiyou
Miao, Lianying
Song, Wenyao
Miao, Zhengke
Powiązania:
https://bibliotekanauki.pl/articles/30148675.pdf
Data publikacji:
2014-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge coloring
edge-chromatic critical graphs
independence number
Opis:
In 1968, Vizing conjectured that for any edge chromatic critical graph $G = (V,E)$ with maximum degree $△$ and independence number $α(G)$, $α(G) ≤ \frac{|V|}{2}$. It is known that $α(G) < \frac{3∆−2}{5∆−2}|V|$. In this paper we improve this bound when $△≥4$. Our precise result depends on the number $n_2$ of 2-vertices in $G$, but in particular we prove that $α(G) ≤\frac{3∆−3}{5∆−3}|V|$ when $△≥5$ and $n_2≤2(△− 1)$.
Źródło:
Discussiones Mathematicae Graph Theory; 2014, 34, 3; 577-584
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
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ł:
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ł
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ł:
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ł:
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ł:
Looseness and Independence Number of Triangulations on Closed Surfaces
Autorzy:
Nakamoto, Atsuhiro
Negami, Seiya
Ohba, Kyoji
Suzuki, Yusuke
Powiązania:
https://bibliotekanauki.pl/articles/31340887.pdf
Data publikacji:
2016-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
triangulations
closed surfaces
looseness
k-loosely tight
independence number
Opis:
The looseness of a triangulation $G$ on a closed surface $ F^2$, denoted by $ \xi (G) $, is defined as the minimum number $k$ such that for any surjection $ c : V (G) \rightarrow {1, 2, . . ., k + 3} $, there is a face $uvw$ of $G$ with $c(u)$, $c(v)$ and $c(w)$ all distinct. We shall bound $ \xi (G) $ for triangulations $G$ on closed surfaces by the independence number of $G$ denoted by $ \alpha(G) $. In particular, for a triangulation $G$ on the sphere, we have $ \xi (G) \le \frac{11 \alpha (G) - 10}{6} $ and this bound is sharp. For a triangulation $G$ on a non-spherical surface $F^2$, we have $ \xi (G) \le 2 \alpha (G) + \mathcal{l}(F^2) − 2 $, where $ \mathcal{l}(F^2) = \floor{ (2 − \chi (F^2))//2 } $ with Euler characteristic $ \chi (F^2) $.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 3; 545-554
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ł
Wyświetlanie 1-15 z 29

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