Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

Wyszukujesz frazę "Hedetniemi, Stephen" wg kryterium: Autor


Wyświetlanie 1-7 z 7
Tytuł:
Domination and independence subdivision numbers of graphs
Autorzy:
Haynes, Teresa
Hedetniemi, Sandra
Hedetniemi, Stephen
Powiązania:
https://bibliotekanauki.pl/articles/743809.pdf
Data publikacji:
2000
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
independence
subdivision numbers
Opis:
The domination subdivision number $sd_γ(G)$ of a graph is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number. Arumugam showed that this number is at most three for any tree, and conjectured that the upper bound of three holds for any graph. Although we do not prove this interesting conjecture, we give an upper bound for the domination subdivision number for any graph G in terms of the minimum degrees of adjacent vertices in G. We then define the independence subdivision number $sd_β(G)$ to equal the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the independence number. We show that for any graph G of order n ≥ 2, either $G = K_{1,m}$ and $sd_β(G) = m$, or $1 ≤ sd_β(G) ≤ 2$. We also characterize the graphs G for which $sd_β(G) = 2$.
Źródło:
Discussiones Mathematicae Graph Theory; 2000, 20, 2; 271-280
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
γ-graphs of graphs
Autorzy:
Fricke, Gerd
Hedetniemi, Sandra
Hedetniemi, Stephen
Hutson, Kevin
Powiązania:
https://bibliotekanauki.pl/articles/743973.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
dominating sets
gamma graphs
Opis:
A set S ⊆ V is a dominating set of a graph G = (V,E) if every vertex in V -S is adjacent to at least one vertex in S. The domination number γ(G) of G equals the minimum cardinality of a dominating set S in G; we say that such a set S is a γ-set. In this paper we consider the family of all γ-sets in a graph G and we define the γ-graph G(γ) = (V(γ), E(γ)) of G to be the graph whose vertices V(γ) correspond 1-to-1 with the γ-sets of G, and two γ-sets, say D₁ and D₂, are adjacent in E(γ) if there exists a vertex v ∈ D₁ and a vertex w ∈ D₂ such that v is adjacent to w and D₁ = D₂ - {w} ∪ {v}, or equivalently, D₂ = D₁ - {v} ∪ {w}. In this paper we initiate the study of γ-graphs of graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 3; 517-531
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Downhill domination in graphs
Autorzy:
Haynes, Teresa W.
Hedetniemi, Stephen T.
Jamieson, Jessie D.
Jamieson, William B.
Powiązania:
https://bibliotekanauki.pl/articles/30148687.pdf
Data publikacji:
2014-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
downhill path
downhill domination number
Opis:
A path $π = (v_1, v_2, . . ., v_{k+1})$ in a graph $G = (V,E)$ is a downhill path if for every $i, 1 ≤ i ≤ k, deg(v_i) ≥ deg(v_{i+1})$, where $deg(v_i)$ denotes the degree of vertex $v_i ∈ V$. The downhill domination number equals the minimum cardinality of a set $S ⊆ V$ having the property that every vertex $v ∈ V$ lies on a downhill path originating from some vertex in $S$. We investigate downhill domination numbers of graphs and give upper bounds. In particular, we show that the downhill domination number of a graph is at most half its order, and that the downhill domination number of a tree is at most one third its order. We characterize the graphs obtaining each of these bounds.
Źródło:
Discussiones Mathematicae Graph Theory; 2014, 34, 3; 603-612
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Rainbow Disconnection in Graphs
Autorzy:
Chartrand, Gary
Devereaux, Stephen
Haynes, Teresa W.
Hedetniemi, Stephen T.
Zhang, Ping
Powiązania:
https://bibliotekanauki.pl/articles/31342243.pdf
Data publikacji:
2018-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge coloring
rainbow connection
rainbow disconnection
Opis:
Let G be a nontrivial connected, edge-colored graph. An edge-cut R of G is called a rainbow cut if no two edges in R are colored the same. An edge-coloring of G is a rainbow disconnection coloring if for every two distinct vertices u and v of G, there exists a rainbow cut in G, where u and v belong to different components of G − R. We introduce and study the rainbow disconnection number rd(G) of G, which is defined as the minimum number of colors required of a rainbow disconnection coloring of G. It is shown that the rainbow disconnection number of a nontrivial connected graph G equals the maximum rainbow disconnection number among the blocks of G. It is also shown that for a nontrivial connected graph G of order n, rd(G) = n−1 if and only if G contains at least two vertices of degree n − 1. The rainbow disconnection numbers of all grids Pm □ Pn are determined. Furthermore, it is shown for integers k and n with 1 ≤ k ≤ n − 1 that the minimum size of a connected graph of order n having rainbow disconnection number k is n + k − 2. Other results and a conjecture are also presented.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 4; 1007-1021
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Self-coalition graphs
Autorzy:
Haynes, Teresa W.
Hedetniemi, Jason T.
Hedetniemi, Stephen T.
McRae, Alice A.
Mohan, Raghuveer
Powiązania:
https://bibliotekanauki.pl/articles/29519279.pdf
Data publikacji:
2023
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
coalitions in graphs
coalition partitions
coalition graphs
domination
Opis:
A coalition in a graph $ G = (V,E) $ consists of two disjoint sets $ V_1 $ and $ V_2 $ of vertices, such that neither $ V_1 $ nor $ V_2 $ is a dominating set, but the union $ V_1 ∪ V_2 $ is a dominating set of $ G $. A coalition partition in a graph $ G $ of order $ n = |V| $ is a vertex partition $ π = {V_1, V_2, . . . , V_k} $ such that every set $ V_i $ either is a dominating set consisting of a single vertex of degree $ n − 1 $, or is not a dominating set but forms a coalition with another set $ V_j $ which is not a dominating set. Associated with every coalition partition $ π $ of a graph $ G $ is a graph called the coalition graph of $ G $ with respect to $ π $, denoted $ CG(G, π) $, the vertices of which correspond one-to-one with the sets $ V_1, V_2, . . . , V_k $ of $ π $ and two vertices are adjacent in $ CG(G, π) $ if and only if their corresponding sets in $ π $ form a coalition. The singleton partition $ π_1 $ of the vertex set of $ G $ is a partition of order $ |V| $, that is, each vertex of $ G $ is in a singleton set of the partition. A graph $ G $ is called a self-coalition graph if $ G $ is isomorphic to its coalition graph $ CG(G, π_1)$, where $π_1$ is the singleton partition of $ G $. In this paper, we characterize self-coalition graphs.
Źródło:
Opuscula Mathematica; 2023, 43, 2; 173-183
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Domination Subdivision Numbers
Autorzy:
Haynes, Teresa
Hedetniemi, Sandra
Hedetniemi, Stephen
Jacobs, David
Knisely, James
van der Merwe, Lucas
Powiązania:
https://bibliotekanauki.pl/articles/743491.pdf
Data publikacji:
2001
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
subdivision
Opis:
A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number $sd_γ(G)$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Arumugam conjectured that $1 ≤ sd_γ(G) ≤ 3$ for any graph G. We give a counterexample to this conjecture. On the other hand, we show that $sd_γ(G) ≤ γ(G)+1$ for any graph G without isolated vertices, and give constant upper bounds on $sd_γ(G)$ for several families of graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2001, 21, 2; 239-253
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Offensive alliances in graphs
Autorzy:
Favaron, Odile
Fricke, Gerd
Goddard, Wayne
Hedetniemi, Sandra
Hedetniemi, Stephen
Kristiansen, Petter
Laskar, Renu
Skaggs, R.
Powiązania:
https://bibliotekanauki.pl/articles/744502.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
alliance
offensive
majority
graph
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 2; 263-275
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
    Wyświetlanie 1-7 z 7

    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