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

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
Content available remote

On the minimal length of the longest trail in a fixed edge-density graph

100%
Szécsi V.
Open Mathematics
|
2013
|
tom 11
|
nr 10
1831-1837
EN
A nearly sharp lower bound on the length of the longest trail in a graph on n vertices and average degree k is given provided the graph is dense enough (k ≥ 12.5).
2
Content available remote

Maximum Edge-Colorings Of Graphs

81%
Jendrol’ S., Vrbjarová M.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
117-125
EN
An r-maximum k-edge-coloring of G is a k-edge-coloring of G having a property that for every vertex v of degree dG(v) = d, d ≥ r, the maximum color, that is present at vertex v, occurs at v exactly r times. The r-maximum index [...] χr′(G) $\chi _r^\prime (G)$ is defined to be the minimum number k of colors needed for an r-maximum k-edge-coloring of graph G. In this paper we show that [...] χr′(G)≤3 $\chi _r^\prime (G) \le 3$ for any nontrivial connected graph G and r = 1 or 2. The bound 3 is tight. All graphs G with [...] χ1′(G)=i $\chi _1^\prime (G) = i$ , i = 1, 2, 3 are characterized. The precise value of the r-maximum index, r ≥ 1, is determined for trees and complete graphs.
3
Content available remote

The Degree-Diameter Problem for Outerplanar Graphs

81%
Dankelmann P., Jonck E., Vetrík T.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
823-834
EN
For positive integers Δ and D we define nΔ,D to be the largest number of vertices in an outerplanar graph of given maximum degree Δ and diameter D. We prove that [...] nΔ,D=ΔD2+O (ΔD2−1) $n_{\Delta ,D} = \Delta ^{{D \over 2}} + O\left( {\Delta ^{{D \over 2} - 1} } \right)$ is even, and [...] nΔ,D=3ΔD−12+O (ΔD−12−1) $n_{\Delta ,D} = 3\Delta ^{{{D - 1} \over 2}} + O\left( {\Delta ^{{{D - 1} \over 2} - 1} } \right)$ if D is odd. We then extend our result to maximal outerplanar graphs by showing that the maximum number of vertices in a maximal outerplanar graph of maximum degree Δ and diameter D asymptotically equals nΔ,D.
4
Content available remote

Saturation Spectrum of Paths and Stars

81%
Faudree J., Faudree R. J., Gould R. J., Jacobson M. S., Thomas B. J.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
811-822
EN
A graph G is H-saturated if H is not a subgraph of G but the addition of any edge from G̅ to G results in a copy of H. The minimum size of an H-saturated graph on n vertices is denoted sat(n,H), while the maximum size is the well studied extremal number, ex(n,H). The saturation spectrum for a graph H is the set of sizes of H saturated graphs between sat(n,H) and ex(n,H). In this paper we completely determine the saturation spectrum of stars and we show the saturation spectrum of paths is continuous from sat(n, Pk) to within a constant of ex(n, Pk) when n is sufficiently large.
5
Content available remote

On the Maximum and Minimum Sizes of a Graph with Givenk-Connectivity

81%
Sun Y.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
623-632
EN
The concept of k-connectivity κk(G), introduced by Chartrand in 1984, is a generalization of the cut-version of the classical connectivity. For an integer k ≥ 2, the k-connectivity of a connected graph G with order n ≥ k is the smallest number of vertices whose removal from G produces a graph with at least k components or a graph with fewer than k vertices. In this paper, we get a sharp upper bound for the size of G with κk(G) = t, where 1 ≤ t ≤ n − k and k ≥ 3; moreover, the unique extremal graph is given. Based on this result, we get the exact values for the maximum size, denoted by g(n, k, t), of a connected graph G with order n and κk(G) = t. We also compute the exact values and bounds for another parameter f(n, k, t) which is defined as the minimum size of a connected graph G with order n and κk(G) = t, where 1 ≤ t ≤ n − k and k ≥ 3.
6
Content available remote

Avoiding rainbow 2-connected subgraphs

81%
Gorgol I.
Open Mathematics
|
2017
|
tom 15
|
nr 1
393-397
EN
While defining the anti-Ramsey number Erdős, Simonovits and Sós mentioned that the extremal colorings may not be unique. In the paper we discuss the uniqueness of the colorings, generalize the idea of their construction and show how to use it to construct the colorings of the edges of complete split graphs avoiding rainbow 2-connected subgraphs. These colorings give the lower bounds for adequate anti-Ramsey numbers.
7
Content available remote

Functions on adjacent vertex degrees of trees with given degree sequence

62%
Wang H.
Open Mathematics
|
2014
|
tom 12
|
nr 11
1656-1663
EN
In this note we consider a discrete symmetric function f(x, y) where $$f(x,a) + f(y,b) \geqslant f(y,a) + f(x,b) for any x \geqslant y and a \geqslant b,$$ associated with the degrees of adjacent vertices in a tree. The extremal trees with respect to the corresponding graph invariant, defined as $$\sum\limits_{uv \in E(T)} {f(deg(u),deg(v))} ,$$ are characterized by the “greedy tree” and “alternating greedy tree”. This is achieved through simple generalizations of previously used ideas on similar questions. As special cases, the already known extremal structures of the Randic index follow as corollaries. The extremal structures for the relatively new sum-connectivity index and harmonic index also follow immediately, some of these extremal structures have not been identified in previous studies.
8
Content available remote

Inverse Problem on the Steiner Wiener Index

62%
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.
9
Content available remote

A characterization of diameter-2-critical graphs with no antihole of length four

62%
Haynes T., Henning M.
Open Mathematics
|
2012
|
tom 10
|
nr 3
1125-1132
EN
A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter-2-critical graphs with no antihole of length four, that is, the diameter-2-critical graphs whose complements have no induced 4-cycle. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph of order n is at most n 2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. As a consequence of our characterization, we prove the Murty-Simon Conjecture for graphs with no antihole of length four.
10
Content available remote

Rainbow Vertex-Connection and Forbidden Subgraphs

52%
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ć.