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

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

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  independence number
help Sortuj według:

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

Distance independence in graphs

100%
Sewell J., Slater P.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 2
397-409
EN
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,...}.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On a special case of Hadwiger's conjecture

80%
Plummer M., Stiebitz M., Toft B.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 2
333-363
EN
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.
3
Content available remote

Coloring Some Finite Sets in ℝn

80%
Balogh J., Kostochka A., Raigorodskii A.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 1
25-31
EN
This note relates to bounds on the chromatic number χ(ℝn) of the Euclidean space, which is the minimum number of colors needed to color all the points in ℝn so that any two points at the distance 1 receive different colors. In [6] a sequence of graphs Gn in ℝn was introduced showing that . For many years, this bound has been remaining the best known bound for the chromatic numbers of some lowdimensional spaces. Here we prove that and find an exact formula for the chromatic number in the case of n = 2k and n = 2k − 1.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On well-covered graphs of odd girth 7 or greater

80%
Randerath B., Vestergaard P.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 1
159-172
EN
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.
5
Content available remote

On the Independence Number of Edge Chromatic Critical Graphs

80%
Pang S., Miao L., Song W., Miao Z.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 3
577-584
EN
In 1968, Vizing conjectured that for any edge chromatic critical graph G = (V,E) with maximum degree △ and independence number α (G), α (G) ≤ [...] . It is known that α (G) < [...] |V |. In this paper we improve this bound when △≥ 4. Our precise result depends on the number n2 of 2-vertices in G, but in particular we prove that α (G) ≤ [...] |V | when △ ≥ 5 and n2 ≤ 2(△− 1)
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Bounds on the global offensive k-alliance number in graphs

80%
Chellali M., Haynes T., Randerath B., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 3
597-613
EN
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.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Complete minors, independent sets, and chordal graphs

80%
Balogh J., Lenz J., Wu H.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 4
639-674
EN
The Hadwiger number h(G) of a graph G is the maximum size of a complete minor of G. Hadwiger's Conjecture states that h(G) ≥ χ(G). Since χ(G) α(G) ≥ |V(G)|, Hadwiger's Conjecture implies that α(G) h(G) ≥ |V(G)|. We show that (2α(G) - ⌈log_{τ}(τα(G)/2)⌉) h(G) ≥ |V(G)| where τ ≍ 6.83. For graphs with α(G) ≥ 14, this improves on a recent result of Kawarabayashi and Song who showed (2α(G) - 2) h(G) ≥ |V(G) | when α(G) ≥ 3.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Chvátal-Erdös type theorems

80%
Faudree J., Faudree R., Gould R., Jacobson M., Magnant C.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 2
245-256
EN
The Chvátal-Erdös theorems imply that if G is a graph of order n ≥ 3 with κ(G) ≥ α(G), then G is hamiltonian, and if κ(G) > α(G), then G is hamiltonian-connected. We generalize these results by replacing the connectivity and independence number conditions with a weaker minimum degree and independence number condition in the presence of sufficient connectivity. More specifically, it is noted that if G is a graph of order n and k ≥ 2 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k²-k)/(k+1), and δ(G) ≥ α(G)+k-2, then G is hamiltonian. It is shown that if G is a graph of order n and k ≥ 3 is a positive integer such that κ(G) ≥ 4k²+1, δ(G) > (n+k²-2k)/k, and δ(G) ≥ α(G)+k-2, then G is hamiltonian-connected. This result supports the conjecture that if G is a graph of order n and k ≥ 3 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k²-2k)/k, and δ(G) ≥ α(G)+k-2, then G is hamiltonian-connected, and the conjecture is verified for k = 3 and 4.
9
Content available remote

On Generalized Sierpiński Graphs

71%
Rodríguez-Velázquez J. A., Rodríguez-Bazan E. D., Estrada-Moreno A.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
547-560
EN
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.
10
Content available remote

Looseness and Independence Number of Triangulations on Closed Surfaces

71%
Nakamoto A., Negami S., Ohba K., Suzuki Y.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 3
545-554
EN
The looseness of a triangulation G on a closed surface F2, denoted by ξ (G), is defined as the minimum number k such that for any surjection c : V (G) → {1, 2, . . . , k + 3}, there is a face uvw of G with c(u), c(v) and c(w) all distinct. We shall bound ξ (G) for triangulations G on closed surfaces by the independence number of G denoted by α(G). In particular, for a triangulation G on the sphere, we have [...] and this bound is sharp. For a triangulation G on a non-spherical surface F2, we have ξ (G) ≤ 2α(G) + l(F2) − 2, where l(F2) = [(2 − χ(F2))/2] with Euler characteristic χ(F2).
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Notes on the independence number in the Cartesian product of graphs

71%
Abay-Asmerom G., Hammack R., Larson C., Taylor D.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 1
25-35
EN
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.
12
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Global alliances and independence in trees

61%
Chellali M., Haynes T.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 1
19-27
EN
A global defensive (respectively, offensive) alliance in a graph G = (V,E) is a set of vertices S ⊆ V with the properties that every vertex in V-S has at least one neighbor in S, and for each vertex v in S (respectively, in V-S) at least half the vertices from the closed neighborhood of v are in S. These alliances are called strong if a strict majority of vertices from the closed neighborhood of v must be in S. For each kind of alliance, the associated parameter is the minimum cardinality of such an alliance. We determine relationships among these four parameters and the vertex independence number for trees.
13
Content available remote

On the Total Graph of Mycielski Graphs, Central Graphs and Their Covering Numbers

51%
Patil H. P., Pandiya Raj R.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
361-371
EN
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.
14
Content available remote

Extending the MAX Algorithm for Maximum Independent Set

51%
Lê N. C., Brause C., Schiermeyer I.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 2
365-386
EN
The maximum independent set problem is an NP-hard problem. In this paper, we consider Algorithm MAX, which is a polynomial time algorithm for finding a maximal independent set in a graph G. We present a set of forbidden induced subgraphs such that Algorithm MAX always results in finding a maximum independent set of G. We also describe two modifications of Algorithm MAX and sets of forbidden induced subgraphs for the new algorithms.
15
Content available remote

The Quest for A Characterization of Hom-Properties of Finite Character

41%
Broere I., Matsoha M. D. V., Heidema J.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 2
479-500
EN
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 → H. Given any graph H, the hom-property →H is the set of H-colourable graphs, i.e., the set of all graphs G satisfying G → H. A graph property P is of finite character if, whenever we have that F ∈ P for every finite induced subgraph F of a graph G, then we have that G ∈ 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 →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 →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.
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ć.