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 set" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 29
Tytuł:
Independent transversal domination in graphs
Autorzy:
Hamid, Ismail
Powiązania:
https://bibliotekanauki.pl/articles/743635.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
dominating set
independent set
independent transversal dominating set
Opis:
A set S ⊆ V of vertices in a graph G = (V, E) is called a dominating set if every vertex in V-S is adjacent to a vertex in S. A dominating set which intersects every maximum independent set in G is called an independent transversal dominating set. The minimum cardinality of an independent transversal dominating set is called the independent transversal domination number of G and is denoted by $γ_{it}(G)$. In this paper we begin an investigation of this parameter.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 1; 5-17
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The hardness of the independence and matching clutter of a graph
Autorzy:
Hambardzumyan, S.
Mkrtchyan, V. V.
Musoyan, V. L.
Sargsyan, H.
Powiązania:
https://bibliotekanauki.pl/articles/952814.pdf
Data publikacji:
2016
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
clutter
hardness
independent set
maximal independent set
matching
maximal matching
Opis:
A clutter (or antichain or Sperner family) L is a pair (V, E), where V is a finite set and E is a family of subsets of V none of which is a subset of another. Usually, the elements of V are called vertices of L, and the elements of E are called edges of L. A subset se of an edge e of a clutter is called recognizing for e, if se is not a subset of another edge. The hardness of an edge e of a clutter is the ratio of the size of e's smallest recognizing subset to the size of e. The hardness of a clutter is the maximum hardness of its edges. We study the hardness of clutters arising from independent sets and matchings of graphs.
Źródło:
Opuscula Mathematica; 2016, 36, 3; 375-397
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Maximum Independent Sets in Direct Products of Cycles or Trees with Arbitrary Graphs
Autorzy:
Paj, Tjaša
Špacapan, Simon
Powiązania:
https://bibliotekanauki.pl/articles/31339257.pdf
Data publikacji:
2015-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
direct product
independent set
Opis:
The direct product of graphs G = (V (G), E(G)) and H = (V (H), E(H)) is the graph, denoted as G×H, with vertex set V (G×H) = V (G)×V (H), where vertices (x1, y1) and (x2, y2) are adjacent in G × H if x1x2 ∈ E(G) and y1y2 ∈ E(H). Let n be odd and m even. We prove that every maximum independent set in Pn×G, respectively Cm×G, is of the form (A×C)∪(B×D), where C and D are nonadjacent in G, and A∪B is the bipartition of Pn respectively Cm. We also give a characterization of maximum independent subsets of Pn × G for every even n and discuss the structure of maximum independent sets in T × G where T is a tree.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 4; 675-688
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Making a Dominating Set of a Graph Connected
Autorzy:
Li, Hengzhe
Wu, Baoyindureng
Yang, Weihua
Powiązania:
https://bibliotekanauki.pl/articles/31342251.pdf
Data publikacji:
2018-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
independent set
dominating set
connected dominating set
Opis:
Let $ G = (V,E) $ be a graph and $ S \subseteq V $. We say that $ S $ is a dominating set of $ G $, if each vertex in $ V \backlash S $ has a neighbor in $S$. Moreover, we say that $S$ is a connected (respectively, 2-edge connected or 2-connected) dominating set of $G$ if $ G[S] $ is connected (respectively, 2-edge connected or 2-connected). The domination (respectively, connected domination, or 2-edge connected domination, or 2-connected domination) number of $G$ is the cardinality of a minimum dominating (respectively, connected dominating, or 2-edge connected dominating, or 2-connected dominating) set of $G$, and is denoted $ \gamma (G) $ (respectively $ \gamma_1 (G) $, or $ \gamma_2^′ (G) $, or $ \gamma_2 (G) $). A well-known result of Duchet and Meyniel states that $ \gamma_1 (G) \le 3 \gamma (G) − 2 $ for any connected graph $G$. We show that if $ \gamma (G) \ge 2 $, then $ \gamma_2^′ (G) \ge 5 \gamma (G) − 4 $ when $G$ is a 2-edge connected graph and $ \gamma_2 (G) \le 11 \gamma (G) − 13 $ when $G$ is a 2-connected triangle-free graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 4; 947-962
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Directed hypergraphs: a tool for researching digraphs and hypergraphs
Autorzy:
Galeana-Sánchez, Hortensia
Manrique, Martín
Powiązania:
https://bibliotekanauki.pl/articles/743191.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hypergraph
strongly independent set
transversal set
kernel
Opis:
In this paper we introduce the concept of directed hypergraph. It is a generalisation of the concept of digraph and is closely related with hypergraphs. The basic idea is to take a hypergraph, partition its edges non-trivially (when possible), and give a total order to such partitions. The elements of these partitions are called levels. In order to preserve the structure of the underlying hypergraph, we ask that only vertices which belong to exactly the same edges may be in the same level of any edge they belong to. Some little adjustments are needed to avoid directed walks within a single edge of the underlying hypergraph, and to deal with isolated vertices.
The concepts of independent set, absorbent set, and transversal set are inherited directly from digraphs.
As a consequence of our results on this topic, we have found both a class of kernel-perfect digraphs with odd cycles and a class of hypergraphs which have a strongly independent transversal set.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 2; 313-335
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Some Results on the Independence Polynomial of Unicyclic Graphs
Autorzy:
Oboudi, Mohammad Reza
Powiązania:
https://bibliotekanauki.pl/articles/31342319.pdf
Data publikacji:
2018-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
independence polynomial
independent set
unicyclic graphs
Opis:
Let $G$ be a simple graph on $n$ vertices. An independent set in a graph is a set of pairwise non-adjacent vertices. The independence polynomial of $G$ is the polynomial $ I(G,x)= \Sigma_{k=0}^n s(G,k)x^k $, where $s(G, k)$ is the number of independent sets of $G$ with size $k$ and $s(G, 0) = 1$. A unicyclic graph is a graph containing exactly one cycle. Let $ C_n $ be the cycle on $n$ vertices. In this paper we study the independence polynomial of unicyclic graphs. We show that among all connected unicyclic graphs $G$ on $n$ vertices (except two of them), $ I(G, t) > I(C_n, t)$ for sufficiently large $t$. Finally for every $ n \ge 3 $ we find all connected graphs $H$ such that $I(H, x) = I(C_n, x) $.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 2; 515-524
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Remarks on Dynamic Monopolies with Given Average Thresholds
Autorzy:
Centeno, Carmen C.
Rautenbach, Dieter
Powiązania:
https://bibliotekanauki.pl/articles/31339133.pdf
Data publikacji:
2015-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
dynamic monopoly
degenerate set
vertex cover
independent set
Opis:
Dynamic monopolies in graphs have been studied as a model for spreading processes within networks. Together with their dual notion, the generalized degenerate sets, they form the immediate generalization of the classical notions of vertex covers and independent sets in a graph. We present results concerning dynamic monopolies in graphs of given average threshold values extending and generalizing previous results of Khoshkhah et al. [On dynamic monopolies of graphs: The average and strict majority thresholds, Discrete Optimization 9 (2012) 77-83] and Zaker [Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs, Discrete Appl. Math. 161 (2013) 2716-2723].
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 1; 133-140
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ł:
Domination, Eternal Domination, and Clique Covering
Autorzy:
Klostermeyer, William F.
Mynhardt, C.M.
Powiązania:
https://bibliotekanauki.pl/articles/31339487.pdf
Data publikacji:
2015-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
dominating set
eternal dominating set
independent set
clique cover
Opis:
Eternal and m-eternal domination are concerned with using mobile guards to protect a graph against infinite sequences of attacks at vertices. Eternal domination allows one guard to move per attack, whereas more than one guard may move per attack in the m-eternal domination model. Inequality chains consisting of the domination, eternal domination, m-eternal domination, independence, and clique covering numbers of graph are explored in this paper. Among other results, we characterize bipartite and triangle-free graphs with domination and eternal domination numbers equal to two, trees with equal m-eternal domination and clique covering numbers, and two classes of graphs with equal domination, eternal domination and clique covering numbers.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 2; 283-300
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Arithmetically maximal independent sets in infinite graphs
Autorzy:
Bylka, Stanisław
Powiązania:
https://bibliotekanauki.pl/articles/744334.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
infinite graph
independent set
arithmetical maximal set
line graph
Opis:
Families of all sets of independent vertices in graphs are investigated. The problem how to characterize those infinite graphs which have arithmetically maximal independent sets is posed. A positive answer is given to the following classes of infinite graphs: bipartite graphs, line graphs and graphs having locally infinite clique-cover of vertices. Some counter examples are presented.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 167-182
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ł:
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 independent sets and non-augmentable paths in directed graphs
Autorzy:
Galeana-Sánchez, H.
Powiązania:
https://bibliotekanauki.pl/articles/744219.pdf
Data publikacji:
1998
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
digraph
independent set
directed path
non-augmentable path
Opis:
We investigate sufficient conditions, and in case that D be an asymmetrical digraph a necessary and sufficient condition for a digraph to have the following property: "In any induced subdigraph H of D, every maximal independent set meets every non-augmentable path". Also we obtain a necessary and sufficient condition for any orientation of a graph G results a digraph with the above property. The property studied in this paper is an instance of the property of a conjecture of J.M. Laborde, Ch. Payan and N.H. Huang: "Every digraph contains an independent set which meets every longest directed path" (1982).
Źródło:
Discussiones Mathematicae Graph Theory; 1998, 18, 2; 171-181
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Independent transversals of longest paths in locally semicomplete and locally transitive digraphs
Autorzy:
Galeana-Sánchez, Hortensia
Gómez, Ricardo
Montellano-Ballesteros, Juan
Powiązania:
https://bibliotekanauki.pl/articles/744431.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
independent set
longest path
locally semicomplete
locally transitive
Opis:
We present several results concerning the Laborde-Payan-Xuang conjecture stating that in every digraph there exists an independent set of vertices intersecting every longest path. The digraphs we consider are defined in terms of local semicompleteness and local transitivity. We also look at oriented graphs for which the length of a longest path does not exceed 4.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 3; 469-480
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Sequential Heuristic Methods for the Maximum Independent Set Problem
Autorzy:
Lê, Ngoc C.
Brause, Christoph
Schiermeyer, Ingo
Powiązania:
https://bibliotekanauki.pl/articles/31341835.pdf
Data publikacji:
2017-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
maximum independent set
heuristic
MIN
MAX
VO
vertex ordering
Opis:
We consider sequential heuristics methods for the Maximum Independent Set (MIS) problem. Three classical algorithms, VO [11], MIN [12], or MAX [6], are revisited. We combine Algorithm MIN with the α-redundant vertex technique[3]. Induced forbidden subgraph sets, under which the algorithms give maximum independent sets, are described. The Caro-Wei bound [4,14] is verified and performance of the algorithms on some special graphs is considered.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 2; 415-426
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