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

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

Wyniki wyszukiwania

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

Spanning trees with many or few colors in edge-colored graphs

100%
Broersma H., Li X.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 2
259-269
EN
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.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Isomorphisms and traversability of directed path graphs

100%
Broersma H., Li X.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 2
215-228
EN
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.
3
Content available remote

On the Rainbow Vertex-Connection

100%
Li X., Shi Y.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
307-313
EN
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 vertexconnected. It was proved that if G is a graph of order n with minimum degree δ, then rvc(G) < 11n/δ. In this paper, we show that rvc(G) ≤ 3n/(δ+1)+5 for [xxx] and n ≥ 290, while rvc(G) ≤ 4n/(δ + 1) + 5 for [xxx] and rvc(G) ≤ 4n/(δ + 1) + C(δ) for 6 ≤ δ ≤ 15, where [xxx]. We also prove that rvc(G) ≤ 3n/4 − 2 for δ = 3, rvc(G) ≤ 3n/5 − 8/5 for δ = 4 and rvc(G) ≤ n/2 − 2 for δ = 5. Moreover, an example constructed by Caro et al. shows that when [xxx] and δ = 3, 4, 5, our bounds are seen to be tight up to additive constants.
4
Content available remote

Graphs with Large Generalized (Edge-)Connectivity

100%
Li X., Mao Y.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 4
931-958
EN
The generalized k-connectivity κ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 λk(G). In this paper, graphs of order n such that [...] for even k are characterized.
5
Content available remote

Rainbow Connection Number of Dense Graphs

81%
Li X., Liu M., Schiermeyer I.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 3
603-611
EN
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) ≤ 3 if |E(G)| ≥ [...] + 2, and rc(G) ≤ 4 if |E(G)| ≥ [...] + 3. These bounds are sharp.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A σ₃ type condition for heavy cycles in weighted graphs

81%
Zhang S., Li X., Broersma H.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 2
159-166
EN
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.
7
Content available remote

The Steiner Wiener Index of A Graph

81%
Li X., Mao Y., Gutman I.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 2
455-465
EN
The Wiener index W(G) of a connected graph G, introduced by Wiener in 1947, is defined as W(G) = ∑u,v∈V(G) d(u, v) where dG(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 ⊆ 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 SWk(G) of G is defined by [...] . Expressions for SWk for some special graphs are obtained. We also give sharp upper and lower bounds of SWk 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.
8
Content available remote

Graphs with 3-Rainbow Index n − 1 and n − 2

81%
Li X., Schiermeyer I., Yang K., Zhao Y.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 1
105-120
EN
Let G = (V (G),E(G)) be a nontrivial connected graph of order n with an edge-coloring c : E(G) → {1, 2, . . . , q}, q ∈ N, where adjacent edges may be colored the same. A tree T in G is a rainbow tree if no two edges of T receive the same color. For a vertex set S ⊆ V (G), a tree connecting S in G is called an S-tree. The minimum number of colors that are needed in an edge-coloring of G such that there is a rainbow S-tree for each k-subset S of V (G) is called the k-rainbow index of G, denoted by rxk(G), where k is an integer such that 2 ≤ k ≤ n. Chartrand et al. got that the k-rainbow index of a tree is n−1 and the k-rainbow index of a unicyclic graph is n−1 or n−2. So there is an intriguing problem: Characterize graphs with the k-rainbow index n − 1 and n − 2. In this paper, we focus on k = 3, and characterize the graphs whose 3-rainbow index is n − 1 and n − 2, respectively.
9
Content available remote

Graphs with 4-Rainbow Index 3 and n − 1

81%
Li X., Schiermeyer I., Yang K., Zhao Y.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 2
387-398
EN
Let G be a nontrivial connected graph with an edge-coloring c : E(G) → {1, 2, . . . , q}, q ∈ ℕ, where adjacent edges may be colored the same. A tree T in G is called a rainbow tree if no two edges of T receive the same color. For a vertex set S ⊆ V (G), a tree that connects S in G is called an S-tree. The minimum number of colors that are needed in an edge-coloring of G such that there is a rainbow S-tree for every set S of k vertices of V (G) is called the k-rainbow index of G, denoted by rxk(G). Notice that a lower bound and an upper bound of the k-rainbow index of a graph with order n is k − 1 and n − 1, respectively. Chartrand et al. got that the k-rainbow index of a tree with order n is n − 1 and the k-rainbow index of a unicyclic graph with order n is n − 1 or n − 2. Li and Sun raised the open problem of characterizing the graphs of order n with rxk(G) = n − 1 for k ≥ 3. In early papers we characterized the graphs of order n with 3-rainbow index 2 and n − 1. In this paper, we focus on k = 4, and characterize the graphs of order n with 4-rainbow index 3 and n − 1, respectively.
10
Content available remote

The 3-Rainbow Index of a Graph

81%
Chen L., Li X., Yang K., Zhao Y.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 1
81-94
EN
Let G be a nontrivial connected graph with an edge-coloring c : E(G) → {1, 2, . . . , q}, q ∈ ℕ, where adjacent edges may be colored the same. A tree T in G is a rainbow tree if no two edges of T receive the same color. For a vertex subset S ⊆ V (G), a tree that connects S in G is called an S-tree. The minimum number of colors that are needed in an edge-coloring of G such that there is a rainbow S-tree for each k-subset S of V (G) is called the k-rainbow index of G, denoted by rxk(G). In this paper, we first determine the graphs of size m whose 3-rainbow index equals m, m − 1, m − 2 or 2. We also obtain the exact values of rx3(G) when G is a regular multipartite complete graph or a wheel. Finally, we give a sharp upper bound for rx3(G) when G is 2-connected and 2-edge connected. Graphs G for which rx3(G) attains this upper bound are determined.
11
Content available remote

Rainbow Connection Number of Graphs with Diameter 3

81%
Li H., Li X., Sun Y.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
141-154
EN
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.
12
Content available remote

Inverse Problem on the Steiner Wiener Index

81%
Li X., Mao Y., Gutman I.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
83-95
EN
The Wiener index W(G) of a connected graph G, introduced by Wiener in 1947, is defined as W(G) =∑u,v∈V (G) dG(u, v), where dG(u, v) is the distance (the length a shortest path) between the vertices u and v in G. For S ⊆ 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 SWk(G) of G is defined as [...] SWk(G)=∑S⊆V(G)|S|=kd(S) $SW_k (G) = \sum\nolimits_{\mathop {S \subseteq V(G)}\limits_{|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 ≥ k such that SWk(G) = w (or SWk(T) = w)? In this paper, we give some solutions to this problem.
13
Content available remote

Rainbow Vertex-Connection and Forbidden Subgraphs

81%
Li W., Li X., Zhang J.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
143-154
EN
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.
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ć.