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: 39

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

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  graph
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Some news about the independence number of a graph

100%
Harant J.
Discussiones Mathematicae Graph Theory
|
2000
|
tom 20
|
nr 1
71-79
EN
For a finite undirected graph G on n vertices some continuous optimization problems taken over the n-dimensional cube are presented and it is proved that their optimum values equal the independence number of G.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Decomposition of complete graphs into factors of diameter two and three

100%
Vukicević D.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 1
37-54
EN
We analyze a minimum number of vertices of a complete graph that can be decomposed into one factor of diameter 2 and k factors of diameter at most 3. We find exact values for k ≤ 4 and the asymptotic value of the ratio of this number and k when k tends to infinity. We also find the asymptotic value of the ratio of the number of vertices of the smallest complete graph that can be decomposed into p factors of diameter 2 and k factors of diameter 3 and number k when p is fixed.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

(H,k) stable graphs with minimum size

100%
Dudek A., Szymański A., Zwonek M.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 1
137-149
EN
Let us call a G (H,k) graph vertex stable if it contains a subgraph H ever after removing any of its k vertices. By Q(H,k) we will denote the minimum size of an (H,k) vertex stable graph. In this paper, we are interested in finding Q(𝓒₃,k), Q(𝓒₄,k), $Q(K_{1,p},k)$ and Q(Kₛ,k).
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

(H,k) stable bipartite graphs with minimum size

100%
Dudek A., Zwonek M.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 3
573-581
EN
Let us call a graph G(H;k) vertex stable if it contains a subgraph H after removing any of its k vertices. In this paper we are interested in finding the $(K_{n,n+1};1)$ (respectively $(K_{n,n};1)$) vertex stable graphs with minimum size.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On domination in graphs

100%
Göring F., Harant J.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
7-12
EN
For a finite undirected graph G on n vertices two continuous optimization problems taken over the n-dimensional cube are presented and it is proved that their optimum values equal the domination number γ of G. An efficient approximation method is developed and known upper bounds on γ are slightly improved.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The cobondage number of a graph

80%
Kulli V., Janakiram B.
Discussiones Mathematicae Graph Theory
|
1996
|
tom 16
|
nr 2
111-117
EN
A set D of vertices in a graph G = (V,E) is a dominating set of G if every vertex in V-D is adjacent to some vertex in D. The domination number γ(G) of G is the minimum cardinality of a dominating set. We define the cobondage number $b_c(G)$ of G to be the minimum cardinality among the sets of edges X ⊆ P₂(V) - E, where P₂(V) = {X ⊆ V:|X| = 2} such that γ(G+X) < γ(G). In this paper, the exact values of b_c(G) for some standard graphs are found and some bounds are obtained. Also, a Nordhaus-Gaddum type result is established.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Weakly P-saturated graphs

80%
Borowiecki M., Sidorowicz E.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 1
17-29
EN
For a hereditary property 𝓟 let $k_{𝓟}(G)$ denote the number of forbidden subgraphs contained in G. A graph G is said to be weakly 𝓟-saturated, if G has the property 𝓟 and there is a sequence of edges of G̅, say $e₁,e₂,...,e_l$, such that the chain of graphs $G = G₀ ⊂ G_0 + e₁ ⊂ G₁ + e₂ ⊂ ... ⊂ G_{l-1} + e_l = G_l = K_n(G_{i+1} = G_i + e_{i+1})$ has the following property: $k_{𝓟}(G_{i+1}) > k_{𝓟}(G_i)$, 0 ≤ i ≤ l-1. In this paper we shall investigate some properties of weakly saturated graphs. We will find upper bound for the minimum number of edges of weakly 𝓓ₖ-saturated graphs of order n. We shall determine the number wsat(n,𝓟) for some hereditary properties.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Some additions to the theory of star partitions of graphs

80%
Bell F., Cvetković D., Rowlinson P., Simić S.
Discussiones Mathematicae Graph Theory
|
1999
|
tom 19
|
nr 2
119-134
EN
This paper contains a number of results in the theory of star partitions of graphs. We illustrate a variety of situations which can arise when the Reconstruction Theorem for graphs is used, considering in particular galaxy graphs - these are graphs in which every star set is independent. We discuss a recursive ordering of graphs based on the Reconstruction Theorem, and point out the significance of galaxy graphs in this connection.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On varieties of graphs

80%
Haviar A., Nedela R.
Discussiones Mathematicae Graph Theory
|
1998
|
tom 18
|
nr 2
209-223
EN
In this paper, we introduce the notion of a variety of graphs closed under isomorphic images, subgraph identifications and induced subgraphs (induced connected subgraphs) firstly and next closed under isomorphic images, subgraph identifications, circuits and cliques. The structure of the corresponding lattices is investigated.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Domination in partitioned graphs

80%
Tuza Z., Vestergaard P.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 1
199-210
EN
Let V₁, V₂ be a partition of the vertex set in a graph G, and let $γ_i$ denote the least number of vertices needed in G to dominate $V_i$. We prove that γ₁+γ₂ ≤ [4/5]|V(G)| for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest possible value of (γ₁+γ₂)/|V(G)| is shown to grow with the order of (logδ)/(δ).
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On Vizing's conjecture

80%
Bresar B.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 1
5-11
EN
A dominating set D for a graph G is a subset of V(G) such that any vertex in V(G)-D has a neighbor in D, and a domination number γ(G) is the size of a minimum dominating set for G. For the Cartesian product G ⃞ H Vizing's conjecture [10] states that γ(G ⃞ H) ≥ γ(G)γ(H) for every pair of graphs G,H. In this paper we introduce a new concept which extends the ordinary domination of graphs, and prove that the conjecture holds when γ(G) = γ(H) = 3.
12
Content available remote

A Sufficient Condition for Graphs to Be SuperK-Restricted Edge Connected

80%
Wang S., Wang M., Zhang L.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
537-545
EN
For a subset S of edges in a connected graph G, S is a k-restricted edge cut if G − S is disconnected and every component of G − S has at least k vertices. The k-restricted edge connectivity of G, denoted by λk(G), is defined as the cardinality of a minimum k-restricted edge cut. Let ξk(G) = min{|[X, X̄]| : |X| = k, G[X] is connected}, where X̄ = V (G)\X. A graph G is super k-restricted edge connected if every minimum k-restricted edge cut of G isolates a component of order exactly k. Let k be a positive integer and let G be a graph of order ν ≥ 2k. In this paper, we show that if |N(u) ∩ N(v)| ≥ k +1 for all pairs u, v of nonadjacent vertices and [...] ξk(G)≤⌊ν2⌋+k $\xi _k (G) \le \left\lfloor {{\nu \over 2}} \right\rfloor + k$ , then G is super k-restricted edge connected.
13
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Acyclic reducible bounds for outerplanar graphs

80%
Borowiecki M., Fiedorowicz A., Hałuszczak M.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 2
219-239
EN
For a given graph G and a sequence 𝓟₁, 𝓟₂,..., 𝓟ₙ of additive hereditary classes of graphs we define an acyclic (𝓟₁, 𝓟₂,...,Pₙ)-colouring of G as a partition (V₁, V₂,...,Vₙ) of the set V(G) of vertices which satisfies the following two conditions: 1. $G[V_i] ∈ 𝓟_i$ for i = 1,...,n, 2. for every pair i,j of distinct colours the subgraph induced in G by the set of edges uv such that $u ∈ V_i$ and $v ∈ V_j$ is acyclic. A class R = 𝓟₁ ⊙ 𝓟₂ ⊙ ... ⊙ 𝓟ₙ is defined as the set of the graphs having an acyclic (𝓟₁, 𝓟₂,...,Pₙ)-colouring. If 𝓟 ⊆ R, then we say that R is an acyclic reducible bound for 𝓟. In this paper we present acyclic reducible bounds for the class of outerplanar graphs.
14
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On long cycles through four prescribed vertices of a polyhedral graph

80%
Harant J., Jendrol' S., Walther H.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 3
441-451
EN
For a 3-connected planar graph G with circumference c ≥ 44 it is proved that G has a cycle of length at least (1/36)c+(20/3) through any four vertices of G.
15
Content available remote

The graph of a totally geodesic foliation

80%
Wolak R.
Annales Polonici Mathematici
|
1994-1995
|
tom 60
|
nr 3
241-247
EN
We study the properties of the graph of a totally geodesic foliation. We limit our considerations to basic properties of the graph, and from them we derive several interesting corollaries on the structure of leaves.
16
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Highly connected counterexamples to a conjecture on α-domination

80%
Tuza Z.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 3
435-440
EN
An infinite class of counterexamples is given to a conjecture of Dahme et al. [1] concerning the minimum size of a dominating vertex set that contains at least a prescribed proportion of the neighbors of each vertex not belonging to the set.
17
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Offensive alliances in graphs

80%
Favaron O., Fricke G., Goddard W., Hedetniemi S., Hedetniemi S., Kristiansen P., Laskar R., Skaggs R.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 2
263-275
EN
A set S is an offensive alliance if for every vertex v in its boundary N(S)- S it holds that the majority of vertices in v's closed neighbourhood are in S. The offensive alliance number is the minimum cardinality of an offensive alliance. In this paper we explore the bounds on the offensive alliance and the strong offensive alliance numbers (where a strict majority is required). In particular, we show that the offensive alliance number is at most 2/3 the order and the strong offensive alliance number is at most 5/6 the order.
18
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Bounds for index of a modified graph

80%
Zhou B.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 2
213-221
EN
If a graph is connected then the largest eigenvalue (i.e., index) generally changes (decreases or increases) if some local modifications are performed. In this paper two types of modifications are considered: (i) for a fixed vertex, t edges incident with it are deleted, while s new edges incident with it are inserted; (ii) for two non-adjacent vertices, t edges incident with one vertex are deleted, while s new edges incident with the other vertex are inserted. Within each case, we provide lower and upper bounds for the indices of the modified graphs, and then give some sufficient conditions for the index to decrease or increase when a graph is modified as above.
19
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Pₘ-saturated bipartite graphs with minimum size

80%
Dudek A., Wojda A.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 2
197-211
EN
A graph G is said to be H-saturated if G is H-free i.e., (G has no subgraph isomorphic to H) and adding any new edge to G creates a copy of H in G. In 1986 L. Kászonyi and Zs. Tuza considered the following problem: for given m and n find the minimum size sat(n;Pₘ) of Pₘ-saturated graph of order n. They gave the number sat(n;Pₘ) for n big enough. We deal with similar problem for bipartite graphs.
20
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The signless Laplacian spectral radius of graphs with given number of cut vertices

80%
Cui L., Fan Y.-Z.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 1
85-93
EN
In this paper, we determine the graph with maximal signless Laplacian spectral radius among all connected graphs with fixed order and given number of cut vertices.
first rewind previous Strona / 2 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ć.