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ę "Li, Xueliang" wg kryterium: Autor


Tytuł:
Spanning trees with many or few colors in edge-colored graphs
Autorzy:
Broersma, Hajo
Li, Xueliang
Powiązania:
https://bibliotekanauki.pl/articles/971955.pdf
Data publikacji:
1997
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge-coloring
spanning tree
matroid (intersection)
complexity
NP-complete
NP-hard
polynomial algorithm
(minimum) dominating set
Opis:
Given a graph G = (V,E) and a (not necessarily proper) edge-coloring of G, we consider the complexity of finding a spanning tree of G with as many different colors as possible, and of finding one with as few different colors as possible. We show that the first problem is equivalent to finding a common independent set of maximum cardinality in two matroids, implying that there is a polynomial algorithm. We use the minimum dominating set problem to show that the second problem is NP-hard.
Źródło:
Discussiones Mathematicae Graph Theory; 1997, 17, 2; 259-269
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Kaleidoscopic Edge-Coloring of Complete Graphs and r-Regular Graphs
Autorzy:
Li, Xueliang
Zhu, Xiaoyu
Powiązania:
https://bibliotekanauki.pl/articles/31343197.pdf
Data publikacji:
2019-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
k -kaleidoscope
regular graph
edge-coloring
Opis:
For an $r$-regular graph $G$, we define an edge-coloring $c$ with colors from ${1, 2, . . ., k}$, in such a way that any vertex of $G$ is incident with at least one edge of each color. The multiset-color $c_m(v)$ of a vertex $v$ is defined as the ordered tuple $ (a_1, a_2, . . ., a_k) $, where $ a_i (1 \le i \le k) $ denotes the number of edges of color $i$ which are incident with $v$ in $G$. Then this edge-coloring $c$ is called a $k$-kaleidoscopic coloring of $G$ if every two distinct vertices in $G$ have different multiset-colors and in this way the graph $G$ is defined as a $k$-kaleidoscope. In this paper, we determine the integer $k$ for a complete graph $ K_n $ to be a $k$-kaleidoscope, and hence solve a conjecture in [P. Zhang, A Kaleidoscopic View of Graph Colorings, (Springer Briefs in Math., New York, 2016)] that for any integers $n$ and $k$ with $ n \ge k + 3 \ge 6 $, the complete graph $ K_n$ is a $k$-kaleidoscope. Then, we construct an $r$-regular 3-kaleidoscope of order \( \binom{r-1}{2} - 1 \) for each integer $ r \ge 7 $, where $ r \equiv 3 (mod 4) $, which solves another conjecture in [P. Zhang, A Kaleidoscopic View of Graph Colorings, (Springer Briefs in Math., New York, 2016)] on the maximum order of $r$-regular 3-kaleidoscopes.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 4; 881-888
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the Rainbow Vertex-Connection
Autorzy:
Li, Xueliang
Shi, Yongtang
Powiązania:
https://bibliotekanauki.pl/articles/30146636.pdf
Data publikacji:
2013-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
rainbow vertex-connection
vertex coloring
minimum degree
2-step dominating set
Opis:
A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection of a connected graph $G$, denoted by $rvc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow vertex-connected. It was proved that if $G$ is a graph of order $n$ with minimum degree $ \delta $, then $ rvc(G) < 11n//\delta$. In this paper, we show that $rvc(G) \le 3n//(δ+1)+5$ for $ \delta \ge \sqrt{n-1} -1 $ and $ n \le 290 $, while $ rvc(G) \le 4n//(δ + 1) + 5 $ for $ 16 \le \delta \le \sqrt{n-1}-2 $ and $ rvc(G) \le 4n//(\delta + 1) + C(\delta) $ for $6 \le \delta \le 15$, where $ C(\delta) = e^\frac{ 3 \log (\delta^3 + 2 \delta^2 +3)-3(\log 3 - 1)}{\delta - 3} - 2$. We also prove that $ rvc(G) \le 3n//4 − 2 $ for $ \delta = 3$, $ rvc(G) \le 3n//5 − 8//5$ for $\delta = 4$ and $rvc(G) \le n//2 − 2$ for $\delta = 5$. Moreover, an example constructed by Caro et al. shows that when $ \delta \ge \sqrt{n-1} - 1 $ and $ \delta = 3, 4, 5 $, our bounds are seen to be tight up to additive constants.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 2; 307-313
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Isomorphisms and traversability of directed path graphs
Autorzy:
Broersma, Hajo
Li, Xueliang
Powiązania:
https://bibliotekanauki.pl/articles/743350.pdf
Data publikacji:
2002
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
directed path graph
line digraph
isomorphism
travers-ability
Opis:
The concept of a line digraph is generalized to that of a directed path graph. The directed path graph Pₖ(D) of a digraph D is obtained by representing the directed paths on k vertices of D by vertices. Two vertices are joined by an arc whenever the corresponding directed paths in D form a directed path on k+1 vertices or form a directed cycle on k vertices in D. In this introductory paper several properties of P₃(D) are studied, in particular with respect to isomorphism and traversability. In our main results, we characterize all digraphs D with P₃(D) ≅ D, we show that P₃(D₁) ≅ P₃(D₂) "almost always" implies D₁ ≅ D₂, and we characterize all digraphs with Eulerian or Hamiltonian P₃-graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2002, 22, 2; 215-228
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graphs with Large Generalized (Edge-)Connectivity
Autorzy:
Li, Xueliang
Mao, Yaping
Powiązania:
https://bibliotekanauki.pl/articles/31340594.pdf
Data publikacji:
2016-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
(edge-)connectivity
Steiner tree
internally disjoint trees
edge-disjoint trees
packing
generalized (edge-)connectivity
Opis:
The generalized $k$-connectivity $ \kappa_k (G) $ of a graph $G$, introduced by Hager in 1985, is a nice generalization of the classical connectivity. Recently, as a natural counterpart, we proposed the concept of generalized $k$-edge-connectivity $ \lambda_k (G)$. In this paper, graphs of order $n$ such that $ \kappa_k (G) = n - k/2 - 1 $ and $ \lambda_k (G) = n - k/2 - 1 $ for even $k$ are characterized.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 4; 931-958
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The Vertex-Rainbow Connection Number of Some Graph Operations
Autorzy:
Li, Hengzhe
Ma, Yingbin
Li, Xueliang
Powiązania:
https://bibliotekanauki.pl/articles/32083892.pdf
Data publikacji:
2021-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
rainbow connection number
vertex-rainbow connection number
Cartesian product
lexicographic product
line graph
Opis:
A path in an edge-colored (respectively vertex-colored) graph G is rainbow (respectively vertex-rainbow) if no two edges (respectively internal vertices) of the path are colored the same. An edge-colored (respectively vertex-colored) graph G is rainbow connected (respectively vertex-rainbow connected) if every two distinct vertices are connected by a rainbow (respectively vertex-rainbow) path. The rainbow connection number rc(G) (respectively vertex-rainbow connection number rvc(G)) of G is the smallest number of colors that are needed in order to make G rainbow connected (respectively vertex-rainbow connected). In this paper, we show that for a connected graph G and any edge e = xy ∈ E(G), rvc(G) ≤ rvc(G − e) ≤ rvc(G) + dG−e(x, y) − 1 if G − e is connected. For any two connected, non-trivial graphs G and H, rad(G□H)−1 ≤ rvc(G□H) ≤ 2rad(G□H), where G□H is the Cartesian product of G and H. For any two non-trivial graphs G and H such that G is connected, rvc(G ◦ H) = 1 if diam(G ◦ H) ≤ 2, rad(G) − 1 ≤ rvc(G ◦ H) ≤ 2rad(G) if diam(G) > 2, where G ◦ H is the lexicographic product of G and H. For the line graph L(G) of a graph G we show that rvc(L(G)) ≤ rc(G), which is the first known nontrivial inequality between the rainbow connection number and vertex-rainbow connection number. Moreover, the bounds reported are tight or tight up to additive constants.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 2; 513-530
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Rainbow Connection Number of Dense Graphs
Autorzy:
Li, Xueliang
Liu, Mengmeng
Schiermeyer, Ingo
Powiązania:
https://bibliotekanauki.pl/articles/30146190.pdf
Data publikacji:
2013-07-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge-colored graph
rainbow coloring
rainbow connection number
Opis:
An edge-colored graph $G$ is rainbow connected, if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph $G$, denoted $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. In this paper we show that $rc(G) \leq 3$ if \( |E(G)| \geq \binom{n-2}{2} + 2 \), and $ rc(G) \leq 4 $ if \( |E(G)| \geq \binom{n-3}{2} + 3 \). These bounds are sharp.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 3; 603-611
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Erdős-Gallai-Type Results for Total Monochromatic Connection of Graphs
Autorzy:
Jiang, Hui
Li, Xueliang
Zhang, Yingying
Powiązania:
https://bibliotekanauki.pl/articles/31343240.pdf
Data publikacji:
2019-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total-colored graph
total monochromatic connection
Erdős- Gallai-type problem
Opis:
A graph is said to be total-colored if all the edges and the vertices of the graph are colored. A total-coloring of a graph is a total monochromatically-connecting coloring (TMC-coloring, for short) if any two vertices of the graph are connected by a path whose edges and internal vertices have the same color. For a connected graph G, the total monochromatic connection number, denoted by tmc(G), is defined as the maximum number of colors used in a TMC-coloring of G. In this paper, we study two kinds of Erdős-Gallai-type problems for tmc(G) and completely solve them.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 4; 775-785
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Rainbow Connection Number of Graphs with Diameter 3
Autorzy:
Li, Hengzhe
Li, Xueliang
Sun, Yuefang
Powiązania:
https://bibliotekanauki.pl/articles/31342160.pdf
Data publikacji:
2017-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge-coloring
rainbow path
rainbow connection number
diameter
Opis:
A path in an edge-colored graph G is rainbow if no two edges of the path are colored the same. The rainbow connection number rc(G) of G is the smallest integer k for which there exists a k-edge-coloring of G such that every pair of distinct vertices of G is connected by a rainbow path. Let f(d) denote the minimum number such that rc(G) ≤ f(d) for each bridgeless graph G with diameter d. In this paper, we shall show that 7 ≤ f(3) ≤ 9.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 1; 141-154
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Rainbow Vertex-Connection and Forbidden Subgraphs
Autorzy:
Li, Wenjing
Li, Xueliang
Zhang, Jingshu
Powiązania:
https://bibliotekanauki.pl/articles/31342433.pdf
Data publikacji:
2018-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
vertex-rainbow path
rainbow vertex-connection
forbidden sub-graphs
Opis:
A path in a vertex-colored graph is called vertex-rainbow if its internal vertices have pairwise distinct colors. A vertex-colored graph G is rainbow vertex-connected if for any two distinct vertices of G, there is a vertex-rainbow path connecting them. For a connected graph G, the rainbow vertex-connection number of G, denoted by rvc(G), is defined as the minimum number of colors that are required to make G rainbow vertex-connected. In this paper, we find all the families ℱ of connected graphs with |ℱ| ∈ {1, 2}, for which there is a constant k such that, for every connected ℱ-free graph G, rvc(G) ≤ diam(G) + k, where diam(G) is the diameter of G.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 1; 143-154
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A σ₃ type condition for heavy cycles in weighted graphs
Autorzy:
Zhang, Shenggui
Li, Xueliang
Broersma, Hajo
Powiązania:
https://bibliotekanauki.pl/articles/743462.pdf
Data publikacji:
2001
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
weighted graph
(long, heavy, Hamilton) cycle
weighted degree
(weighted) degree sum
Opis:
A weighted graph is a graph in which each edge e is assigned a non-negative number w(e), called the weight of e. The weight of a cycle is the sum of the weights of its edges. The weighted degree $d^w(v)$ of a vertex v is the sum of the weights of the edges incident with v. In this paper, we prove the following result: Suppose G is a 2-connected weighted graph which satisfies the following conditions: 1. The weighted degree sum of any three independent vertices is at least m; 2. w(xz) = w(yz) for every vertex z ∈ N(x)∩N(y) with d(x,y) = 2; 3. In every triangle T of G, either all edges of T have different weights or all edges of T have the same weight. Then G contains either a Hamilton cycle or a cycle of weight at least 2m/3. This generalizes a theorem of Fournier and Fraisse on the existence of long cycles in k-connected unweighted graphs in the case k = 2. Our proof of the above result also suggests a new proof to the theorem of Fournier and Fraisse in the case k = 2.
Źródło:
Discussiones Mathematicae Graph Theory; 2001, 21, 2; 159-166
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The Steiner Wiener Index of A Graph
Autorzy:
Li, Xueliang
Mao, Yaping
Gutman, Ivan
Powiązania:
https://bibliotekanauki.pl/articles/31340916.pdf
Data publikacji:
2016-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
distance
Steiner distance
Wiener index
Steiner Wiener k- index
Opis:
The Wiener index $ W(G) $ of a connected graph $G$, introduced by Wiener in 1947, is defined as $ W(G) = \Sigma_{ u,v \in V(G) } d(u, v) $ where $ d_G(u, v) $ is the distance between vertices $u$ and $v$ of $G$. The Steiner distance in a graph, introduced by Chartrand et al. in 1989, is a natural generalization of the concept of classical graph distance. For a connected graph $G$ of order at least 2 and $ S \subseteq V (G) $, the Steiner distance $d(S)$ of the vertices of $S$ is the minimum size of a connected subgraph whose vertex set is $S$. We now introduce the concept of the Steiner Wiener index of a graph. The Steiner k-Wiener index $ SW_k(G) $ of $ G $ is defined by $ \Sigma_{ S \subseteq V(G) \ |S| = k } \ d(S) $. Expressions for $ SW_k $ for some special graphs are obtained. We also give sharp upper and lower bounds of $ SW_k $ of a connected graph, and establish some of its properties in the case of trees. An application in chemistry of the Steiner Wiener index is reported in our another paper.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 2; 455-465
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Inverse Problem on the Steiner Wiener Index
Autorzy:
Li, Xueliang
Mao, Yaping
Gutman, Ivan
Powiązania:
https://bibliotekanauki.pl/articles/31342440.pdf
Data publikacji:
2018-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
distance
Steiner distance
Wiener index
Steiner Wiener index
Opis:
The Wiener index $ W(G) $ of a connected graph $G$, introduced by Wiener in 1947, is defined as $ W(G) = \Sigma_{ u,v \in V (G) } \ d_G(u, v) $, where $ d_G(u, v) $ is the distance (the length a shortest path) between the vertices $u$ and $v$ in $G$. For $ S \subseteq V (G) $, the Steiner distance $d(S)$ of the vertices of $S$, introduced by Chartrand et al. in 1989, is the minimum size of a connected subgraph of $G$ whose vertex set contains $S$. The $k$-th Steiner Wiener index $ SW_k(G) $ of $G$ is defined as $ SW_k(G)= \Sigma_{ S \subseteq V(G) \ |S|=k } \ d(S) $. We investigate the following problem: Fixed a positive integer $k$, for what kind of positive integer w does there exist a connected graph $G$ (or a tree $T$) of order $ n \ge k$ such that $ SW_k(G) = w$ (or $ SW_k(T) = w$)? In this paper, we give some solutions to this problem.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 1; 83-95
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Generalized Rainbow Connection of Graphs and their Complements
Autorzy:
Li, Xueliang
Magnant, Colton
Wei, Meiqin
Zhu, Xiaoyu
Powiązania:
https://bibliotekanauki.pl/articles/31342420.pdf
Data publikacji:
2018-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
ℓ-rainbow path
( k, ℓ)-rainbow connected
( k, ℓ)-rainbow connection number
Opis:
Let $G$ be an edge-colored connected graph. A path $P$ in $G$ is called $ \mathcal{l} $-rainbow if each subpath of length at most $ \mathcal{l} + 1 $ is rainbow. The graph $G$ is called $(k, \mathcal{l} )$-rainbow connected if there is an edge-coloring such that every pair of distinct vertices of $G$ is connected by $k$ pairwise internally vertex-disjoint $ \mathcal{l} $-rainbow paths in $G$. The minimum number of colors needed to make $G$ $(k, \mathcal{l})$-rainbow connected is called the $ (k, \mathcal{l} )$-rainbow connection number of $G$ and denoted by $ rc_{ k,\mathcal{l} } (G) $. In this paper, we first focus on the (1, 2)-rainbow connection number of $G$ depending on some constraints of $ \overline{G} $. Then, we characterize the graphs of order $n$ with (1, 2)-rainbow connection number $ n − 1 $ or $ n − 2 $. Using this result, we investigate the Nordhaus-Gaddum-Type problem of (1, 2)-rainbow connection number and prove that $ rc_{1,2}(G) + rc_{1,2}( \overlina{G} ) \le n + 2 $ for connected graphs $ G $ and $ \overline{G} $. The equality holds if and only if $G$ or $ \overline{G} $ is isomorphic to a double star.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 2; 371-384
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Proper (Strong) Rainbow Connection of Graphs
Autorzy:
Jiang, Hui
Li, Wenjing
Li, Xueliang
Magnant, Colton
Powiązania:
https://bibliotekanauki.pl/articles/32083886.pdf
Data publikacji:
2021-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
proper (strong) rainbow connection number
Cartesian product
chromatic index
Opis:
A path in an edge-colored graph $G$ is called a rainbow path if no two edges on the path have the same color. The graph $G$ is called rainbow connected if between every pair of distinct vertices of $G$, there is a rainbow path. Recently, Johnson et al. considered this concept with the additional requirement that the coloring of $G$ is proper. The proper rainbow connection number of $G$, denoted by $prc(G)$, is the minimum number of colors needed to properly color the edges of $G$ so that $G$ is rainbow connected. Similarly, the proper strong rainbow connection number of $G$, denoted by $psrc(G)$, is the minimum number of colors needed to properly color the edges of $G$ such that for any two distinct vertices of $G$, there is a rainbow geodesic (shortest path) connecting them. In this paper, we characterize those graphs with proper rainbow connection numbers equal to the size or within 1 of the size. Moreover, we completely solve a question proposed by Johnson et al. by proving that if \(G = K_{p1} \Box \dots \Box K_{pn}\), where $n≥ 1$, and $p_1, . . ., p_n>1$ are integers, then $prc(G) = psrc(G) = χ^′(G)$, where $χ^′(G)$ denotes the chromatic index of $G$. Finally, we investigate some suffcient conditions for a graph $G$ to satisfy $prc(G) = rc(G)$, and make some slightly positive progress by using a relation between $rc(G)$ and the girth of the graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 2; 469-479
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