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ę "star graph" wg kryterium: Temat


Tytuł:
On Ambarzumian type theorems for tree domains
Autorzy:
Pivovarchik, Vyacheslav
Powiązania:
https://bibliotekanauki.pl/articles/2216192.pdf
Data publikacji:
2022
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
Sturm-Liouville equation
eigenvalue
equilateral tree
star graph
Dirichlet boundary condition
Neumann boundary condition
Opis:
It is known that the spectrum of the spectral Sturm–Liouville problem on an equilateral tree with (generalized) Neumann’s conditions at all vertices uniquely determines the potentials on the edges in the unperturbed case, i.e. case of the zero potentials on the edges (Ambarzumian’s theorem). This case is exceptional, and in general case (when the Dirichlet conditions are imposed at some of the pendant vertices) even two spectra of spectral problems do not determine uniquely the potentials on the edges. We consider the spectral Sturm–Liouville problem on an equilateral tree rooted at its pendant vertex with (generalized) Neumann conditions at all vertices except of the root and the Dirichlet condition at the root. In this case Ambarzumian’s theorem can’t be applied. We show that if the spectrum of this problem is unperturbed, the spectrum of the Neumann-Dirichlet problem on the root edge is also unperturbed and the spectra of the problems on the complimentary subtrees with (generalized) Neumann conditions at all vertices except the subtrees’ roots and the Dirichlet condition at the subtrees’ roots are unperturbed then the potential on each edge of the tree is 0 almost everywhere.
Źródło:
Opuscula Mathematica; 2022, 42, 3; 427-437
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The Complexity of Secure Domination Problem in Graphs
Autorzy:
Wang, Haichao
Zhao, Yancai
Deng, Yunping
Powiązania:
https://bibliotekanauki.pl/articles/31342335.pdf
Data publikacji:
2018-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
secure domination
star convex bipartite graph
doubly chordal graph
NP-complete
APX-complete
Opis:
A dominating set of a graph G is a subset D ⊆ V (G) such that every vertex not in D is adjacent to at least one vertex in D. A dominating set S of G is called a secure dominating set if each vertex u ∈ V (G) \ S has one neighbor v in S such that (S \ {v}) ∪ {u} is a dominating set of G. The secure domination problem is to determine a minimum secure dominating set of G. In this paper, we first show that the decision version of the secure domination problem is NP-complete for star convex bipartite graphs and doubly chordal graphs. We also prove that the secure domination problem cannot be approximated within a factor of (1−ε) ln |V | for any ε > 0, unless NP⊆DTIME (|V |O(log log |V|)). Finally, we show that the secure domination problem is APX-complete for bounded degree graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 2; 385-396
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On local structure of 1-planar graphs of minimum degree 5 and girth 4
Autorzy:
Hudák, Dávid
Madaras, Tomás
Powiązania:
https://bibliotekanauki.pl/articles/744412.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
light graph
1-planar graph
star
cycle
Opis:
A graph is 1-planar if it can be embedded in the plane so that each edge is crossed by at most one other edge. We prove that each 1-planar graph of minimum degree 5 and girth 4 contains
(1) a 5-vertex adjacent to an ≤ 6-vertex,
(2) a 4-cycle whose every vertex has degree at most 9,
(3) a $K_{1,4}$ with all vertices having degree at most 11.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 2; 385-400
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Some additions to the theory of star partitions of graphs
Autorzy:
Bell, Francis
Cvetković, Dragos
Rowlinson, Peter
Simić, Slobodan
Powiązania:
https://bibliotekanauki.pl/articles/744251.pdf
Data publikacji:
1999
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph
eigenvalues
eigenspaces
star partitions
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 1999, 19, 2; 119-134
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the Star Chromatic Index of Generalized Petersen Graphs
Autorzy:
Zhu, Enqiang
Shao, Zehui
Powiązania:
https://bibliotekanauki.pl/articles/32083878.pdf
Data publikacji:
2021-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
star edge-coloring
star chromatic index
generalized Petersen graph
Opis:
The star $k$-edge-coloring of graph $G$ is a proper edge coloring using $k$ colors such that no path or cycle of length four is bichromatic. The minimum number $k$ for which $G$ admits a star $k$-edge-coloring is called the star chromatic index of $G$, denoted by $χ_s^′(G)$. Let $GCD(n, k)$ be the greatest common divisor of $n$ and $k$. In this paper, we give a necessary and sufficient condition of $χ_s^′(P(n, k)) = 4$ for a generalized Petersen graph $P(n, k)$ and show that “almost all” generalized Petersen graphs have a star 5-edge-colorings. Furthermore, for any two integers $k$ and $n(≥2k + 1)$ such that $GCD(n, k) ≥ 3, P (n, k)$ has a star 5-edge-coloring, with the exception of the case that $GCD(n, k) = 3$, $k ≠ GCD(n, k)$ and \(\frac{n}{3}≡1(mod3)\).
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 2; 427-439
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Decompositions of Complete Bipartite Graphs and Complete Graphs Into Paths, Stars, and Cycles with Four Edges Each
Autorzy:
Shyu, Tay-Woei
Powiązania:
https://bibliotekanauki.pl/articles/32083883.pdf
Data publikacji:
2021-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
complete graph
complete bipartite graph
path
star
cycle
decomposition
Opis:
Let G be either a complete graph of odd order or a complete bipartite graph in which each vertex partition has an even number of vertices. In this paper, we determine the set of triples (p, q, r), with p, q, r > 0, for which there exists a decomposition of G into p paths, q stars, and r cycles, each of which has 4 edges.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 2; 451-468
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Trees as Star Complements in Regular Graphs
Autorzy:
Rowlinson, Peter
Powiązania:
https://bibliotekanauki.pl/articles/31562766.pdf
Data publikacji:
2020-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
eigenvalue
regular graph
star complement
tree
Opis:
Let G be a connected r-regular graph (r > 3) of order n with a tree of order t as a star complement for an eigenvalue µ ∉ {−1, 0}. It is shown that n ≤ 1/2 (r + 1)t − 2. Equality holds when G is the complement of the Clebsch graph (with µ = 1, r = 5, t = 6, n = 16).
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 2; 621-636
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Star-Cycle Factors of Graphs
Autorzy:
Egawa, Yoshimi
Kano, Mikio
Yan, Zheng
Powiązania:
https://bibliotekanauki.pl/articles/30147223.pdf
Data publikacji:
2014-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
star factor
cycle factor
star-cycle factor
factor of graph
Opis:
A spanning subgraph $F$ of a graph $G$ is called a star-cycle factor of $G$ if each component of $F$ is a star or cycle. Let $G$ be a graph and $f : V (G) → {1, 2, 3, . . .}$ be a function. Let $W = {v ∈ V (G) : f(v) = 1}$. Under this notation, it was proved by Berge and Las Vergnas that G has a star-cycle factor $F$ with the property that (i) if a component $D$ of $F$ is a star with center $v$, then $deg_F (v) ≤ f(v)$, and (ii) if a component $D$ of $F$ is a cycle, then $V (D) ⊆ W$ if and only if $iso(G − S) ≤ Σ_{x∈S} f(x)$ for all $S ⊂ V (G)$, where $iso(G − S)$ denotes the number of isolated vertices of $G − S$. They proved this result by using circulation theory of flows and fractional factors of graphs. In this paper, we give an elementary and short proof of this theorem.
Źródło:
Discussiones Mathematicae Graph Theory; 2014, 34, 1; 193-198
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On light subgraphs in plane graphs of minimum degree five
Autorzy:
Jendrol', Stanislav
Madaras, Tomáš
Powiązania:
https://bibliotekanauki.pl/articles/972033.pdf
Data publikacji:
1996
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
planar graph
light subgraph
star
triangulation
Opis:
A subgraph of a plane graph is light if the sum of the degrees of the vertices of the subgraph in the graph is small. It is well known that a plane graph of minimum degree five contains light edges and light triangles. In this paper we show that every plane graph of minimum degree five contains also light stars $K_{1,3}$ and $K_{1,4}$ and a light 4-path P₄. The results obtained for $K_{1,3}$ and P₄ are best possible.
Źródło:
Discussiones Mathematicae Graph Theory; 1996, 16, 2; 207-217
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number
Autorzy:
Broersma, Hajo
Marchal, Bert
Paulusma, Daniel
Salman, A.
Powiązania:
https://bibliotekanauki.pl/articles/743123.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
backbone coloring
split graph
matching
star
Opis:
We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph G = (V,E) and a spanning subgraph H of G (the backbone of G), a λ-backbone coloring for G and H is a proper vertex coloring V→ {1,2,...} of G in which the colors assigned to adjacent vertices in H differ by at least λ. The algorithmic and combinatorial properties of backbone colorings have been studied for various types of backbones in a number of papers. The main outcome of earlier studies is that the minimum number l of colors, for which such colorings V→ {1,2,...,l} exist, in the worst case is a factor times the chromatic number (for path, tree, matching and star backbones). We show here that for split graphs and matching or star backbones, l is at most a small additive constant (depending on λ) higher than the chromatic number. Our proofs combine algorithmic and combinatorial arguments. We also indicate other graph classes for which our results imply better upper bounds on l than the previously known bounds.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 1; 143-162
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Wiener index of generalized stars and their quadratic line graphs
Autorzy:
Dobrynin, Andrey
Mel'nikov, Leonid
Powiązania:
https://bibliotekanauki.pl/articles/743914.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
distance in a graph
Wiener index
star
iterated line graph
Opis:
The Wiener index, W, is the sum of distances between all pairs of vertices in a graph G. The quadratic line graph is defined as L(L(G)), where L(G) is the line graph of G. A generalized star S is a tree consisting of Δ ≥ 3 paths with the unique common endvertex. A relation between the Wiener index of S and of its quadratic graph is presented. It is shown that generalized stars having the property W(S) = W(L(L(S)) exist only for 4 ≤ Δ ≤ 6. Infinite families of generalized stars with this property are constructed.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 1; 161-175
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Star Coloring Outerplanar Bipartite Graphs
Autorzy:
Ramamurthi, Radhika
Sanders, Gina
Powiązania:
https://bibliotekanauki.pl/articles/31343188.pdf
Data publikacji:
2019-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
chromatic number
star coloring
outerplanar bipartite graph
Opis:
A proper coloring of the vertices of a graph is called a star coloring if at least three colors are used on every 4-vertex path. We show that all outerplanar bipartite graphs can be star colored using only five colors and construct the smallest known example that requires five colors.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 4; 899-908
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Strong ƒ-Star Factors of Graphs
Autorzy:
Yan, Zheng
Powiązania:
https://bibliotekanauki.pl/articles/31339350.pdf
Data publikacji:
2015-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
ƒ-star factor
strong ƒ-star factor
complete-cactus
factor of graph
Opis:
Let G be a graph and f : V (G) → {2, 3, . . .}. A spanning subgraph F is called strong f-star of G if each component of F is a star whose center x satisfies degF (x) ≤ ƒ(x) and F is an induced subgraph of G. In this paper, we prove that G has a strong f-star factor if and only if oddca(G − S) ≤ ∑x∊S ƒ(x) for all S ⊂ V (G), where oddca(G) denotes the number of odd complete-cacti of G.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 3; 475-482
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
All Tight Descriptions of 3-Stars in 3-Polytopes with Girth 5
Autorzy:
Borodin, Oleg V.
Ivanova, Anna O.
Powiązania:
https://bibliotekanauki.pl/articles/31342193.pdf
Data publikacji:
2017-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
3-polytope
planar graph
structure properties
k -star
Opis:
Lebesgue (1940) proved that every 3-polytope P5 of girth 5 has a path of three vertices of degree 3. Madaras (2004) refined this by showing that every P5 has a 3-vertex with two 3-neighbors and the third neighbor of degree at most 4. This description of 3-stars in P5s is tight in the sense that no its parameter can be strengthened due to the dodecahedron combined with the existence of a P5 in which every 3-vertex has a 4-neighbor. We give another tight description of 3-stars in P5s: there is a vertex of degree at most 4 having three 3-neighbors. Furthermore, we show that there are only these two tight descriptions of 3-stars in P5s. Also, we give a tight description of stars with at least three rays in P5s and pose a problem of describing all such descriptions. Finally, we prove a structural theorem about P5s that might be useful in further research.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 1; 5-12
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
List Star Edge-Coloring of Subcubic Graphs
Autorzy:
Kerdjoudj, Samia
Kostochka, Alexandr
Raspaud, André
Powiązania:
https://bibliotekanauki.pl/articles/31342241.pdf
Data publikacji:
2018-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph coloring
edge coloring
star coloring
planar graphs
Opis:
A star edge-coloring of a graph $ G $ is a proper edge coloring such that every 2-colored connected subgraph of $ G $ is a path of length at most 3. For a graph $ G $, let the list star chromatic index of $ G $, $ ch_{st}^' (G) $, be the minimum $k$ such that for any $k$-uniform list assignment $L$ for the set of edges, $G$ has a star edge-coloring from L. Dvořák, Mohar and Šámal asked whether the list star chromatic index of every subcubic graph is at most 7. We prove that it is at most 8. We also prove that if the maximum average degree of a subcubic graph $G$ is less than \( \tfrac{7}{3} \) (respectively, \( \tfrac{5}{2} \)), then $ ch_{st}^' (G) \le 5 $ (respectively, $ ch_{st}^' (G) \le 6 $).
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 4; 1037-1054
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł

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