Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 11

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  independent set
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote

Maximum Independent Sets in Direct Products of Cycles or Trees with Arbitrary Graphs

100%
Paj T., Špacapan S.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 4
675-688
EN
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.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Remarks on partially square graphs, hamiltonicity and circumference

80%
Kheddouci H.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 2
255-266
EN
Given a graph G, its partially square graph G* is a graph obtained by adding an edge (u,v) for each pair u, v of vertices of G at distance 2 whenever the vertices u and v have a common neighbor x satisfying the condition $N_G(x) ⊆ N_G[u] ∪ N_G[v]$, where $N_G[x] = N_G(x) ∪ {x}$. In the case where G is a claw-free graph, G* is equal to G². We define $σ°ₜ = min{ ∑_{x∈S} d_G(x):S is an independent set in G* and |S| = t}$. We give for hamiltonicity and circumference new sufficient conditions depending on σ° and we improve some known results.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On independent sets and non-augmentable paths in directed graphs

80%
Galeana-Sánchez H.
Discussiones Mathematicae Graph Theory
|
1998
|
tom 18
|
nr 2
171-181
EN
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).
4
Content available remote

The ramsey number for theta graph versus a clique of order three and four

80%
Bataineh M. S. A., Jaradat M. M. M., Bateeha M. S.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 2
223-232
EN
For any two graphs F1 and F2, the graph Ramsey number r(F1, F2) is the smallest positive integer N with the property that every graph on at least N vertices contains F1 or its complement contains F2 as a subgraph. In this paper, we consider the Ramsey numbers for theta-complete graphs. We determine r(θn,Km) for m = 2, 3, 4 and n > m. More specifically, we establish that r(θn,Km) = (n − 1)(m − 1) + 1 for m = 3, 4 and n > m
5
Content available remote

Domination, Eternal Domination, and Clique Covering

80%
Klostermeyer W. F., Mynhardt C. M.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 2
283-300
EN
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.
6
Content available remote

Remarks on Dynamic Monopolies with Given Average Thresholds

80%
Centeno C. C., Rautenbach D.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 1
133-140
EN
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].
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Independent transversals of longest paths in locally semicomplete and locally transitive digraphs

80%
Galeana-Sánchez H., Gómez R., Montellano-Ballesteros J.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 3
469-480
EN
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.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Arithmetically maximal independent sets in infinite graphs

80%
Bylka S.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
167-182
EN
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.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Independent transversal domination in graphs

80%
Hamid I.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 1
5-17
EN
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.
10
Content available remote

Independent Detour Transversals in 3-Deficient Digraphs

70%
van Aardt S., Frick M., Singleton J.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
261-275
EN
In 1982 Laborde, Payan and Xuong [Independent sets and longest directed paths in digraphs, in: Graphs and other combinatorial topics (Prague, 1982) 173-177 (Teubner-Texte Math., 59 1983)] conjectured that every digraph has an independent detour transversal (IDT), i.e. an independent set which intersects every longest path. Havet [Stable set meeting every longest path, Discrete Math. 289 (2004) 169-173] showed that the conjecture holds for digraphs with independence number two. A digraph is p-deficient if its order is exactly p more than the order of its longest paths. It follows easily from Havet’s result that for p = 1, 2 every p-deficient digraph has an independent detour transversal. This paper explores the existence of independent detour transversals in 3-deficient digraphs.
11
Content available remote

Counting Maximal Distance-Independent Sets in Grid Graphs

70%
Euler R., Oleksik P., Skupień Z.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 3
531-557
EN
Previous work on counting maximal independent sets for paths and certain 2-dimensional grids is extended in two directions: 3-dimensional grid graphs are included and, for some/any ℓ ∈ N, maximal distance-ℓ independent (or simply: maximal ℓ-independent) sets are counted for some grids. The transfer matrix method has been adapted and successfully applied
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.