Wyniki wyszukiwania

1

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Spanning caterpillars with bounded diameter

100%

Faudree R., Gould R., Jacobson M., Lesniak L.

Discussiones Mathematicae Graph Theory

|

1995

|

tom 15

|

nr 2

111-118

EN

A caterpillar is a tree with the property that the vertices of degree at least 2 induce a path. We show that for every graph G of order n, either G or G̅ has a spanning caterpillar of diameter at most 2 log n. Furthermore, we show that if G is a graph of diameter 2 (diameter 3), then G contains a spanning caterpillar of diameter at most $cn^{3/4}$ (at most n).

2

Distance-Locally Disconnected Graphs

80%

Miller M., Ryan J., Ryjáček Z.

Discussiones Mathematicae Graph Theory

|

2013

|

tom 33

|

nr 1

203-215

EN

For an integer k ≥ 1, we say that a (finite simple undirected) graph G is k-distance-locally disconnected, or simply k-locally disconnected if, for any x ∈ V (G), the set of vertices at distance at least 1 and at most k from x induces in G a disconnected graph. In this paper we study the asymptotic behavior of the number of edges of a k-locally disconnected graph on n vertices. For general graphs, we show that this number is Θ(n2) for any fixed value of k and, in the special case of regular graphs, we show that this asymptotic rate of growth cannot be achieved. For regular graphs, we give a general upper bound and we show its asymptotic sharpness for some values of k. We also discuss some connections with cages.

3

Connected partition dimensions of graphs

80%

Saenpholphat V., Zhang P.

Discussiones Mathematicae Graph Theory

|

2002

|

tom 22

|

nr 2

305-323

EN

For a vertex v of a connected graph G and a subset S of V(G), the distance between v and S is d(v,S) = min{d(v,x)|x ∈ S}. For an ordered k-partition Π = {S₁,S₂,...,Sₖ} of V(G), the representation of v with respect to Π is the k-vector r(v|Π) = (d(v,S₁), d(v,S₂),..., d(v,Sₖ)). The k-partition Π is a resolving partition if the k-vectors r(v|Π), v ∈ V(G), are distinct. The minimum k for which there is a resolving k-partition of V(G) is the partition dimension pd(G) of G. A resolving partition Π = {S₁,S₂,...,Sₖ} of V(G) is connected if each subgraph $⟨S_i⟩$ induced by $S_i$ (1 ≤ i ≤ k) is connected in G. The minimum k for which there is a connected resolving k-partition of V(G) is the connected partition dimension cpd(G) of G. Thus 2 ≤ pd (G) ≤ cpd(G) ≤ n for every connected graph G of order n ≥ 2. The connected partition dimensions of several classes of well-known graphs are determined. It is shown that for every pair a, b of integers with 3 ≤ a ≤ b ≤ 2a-1, there is a connected graph G having pd(G) = a and cpd(G) = b. Connected graphs of order n ≥ 3 having connected partition dimension 2, n, or n-1 are characterized.

4

The Steiner Wiener Index of A Graph

80%

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.

5

Inverse Problem on the Steiner Wiener Index

80%

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.

6

Closed k-stop distance in graphs

80%

Bullington G., Eroh L., Gera R., Winters S.

Discussiones Mathematicae Graph Theory

|

2011

|

tom 31

|

nr 3

533-545

EN

The Traveling Salesman Problem (TSP) is still one of the most researched topics in computational mathematics, and we introduce a variant of it, namely the study of the closed k-walks in graphs. We search for a shortest closed route visiting k cities in a non complete graph without weights. This motivates the following definition. Given a set of k distinct vertices 𝓢 = {x₁, x₂, ...,xₖ} in a simple graph G, the closed k-stop-distance of set 𝓢 is defined to be $dₖ(𝓢) = min_{Θ ∈ 𝓟(𝓢)} (d(Θ(x₁),Θ(x₂)) + d(Θ(x₂),Θ(x₃)) + ...+ d(Θ(xₖ),Θ(x₁)))$, where 𝓟(𝓢) is the set of all permutations from 𝓢 onto 𝓢. That is the same as saying that dₖ(𝓢) is the length of the shortest closed walk through the vertices {x₁, ...,xₖ}. Recall that the Steiner distance sd(𝓢) is the number of edges in a minimum connected subgraph containing all of the vertices of 𝓢. We note some relationships between Steiner distance and closed k-stop distance. The closed 2-stop distance is twice the ordinary distance between two vertices. We conjecture that radₖ(G) ≤ diamₖ(G) ≤ k/(k -1) radₖ(G) for any connected graph G for k ≤ 2. For k = 2, this formula reduces to the classical result rad(G) ≤ diam(G) ≤ 2rad(G). We prove the conjecture in the cases when k = 3 and k = 4 for any graph G and for k ≤ 3 when G is a tree. We consider the minimum number of vertices with each possible 3-eccentricity between rad₃(G) and diam₃(G). We also study the closed k-stop center and closed k-stop periphery of a graph, for k = 3.

7

The Median Problem on k-Partite Graphs

71%

Pravas K., Vijayakumar A.

Discussiones Mathematicae Graph Theory

|

2015

|

tom 35

|

nr 3

439-446

EN

In a connected graph G, the status of a vertex is the sum of the distances of that vertex to each of the other vertices in G. The subgraph induced by the vertices of minimum (maximum) status in G is called the median (anti-median) of G. The median problem of graphs is closely related to the optimization problems involving the placement of network servers, the core of the entire networks. Bipartite graphs play a significant role in designing very large interconnection networks. In this paper, we answer a problem on the structure of medians of bipartite graphs by showing that any bipartite graph is the median (or anti-median) of another bipartite graph. Also, with a different construction, we show that the similar results hold for k-partite graphs, k ≥ 3. In addition, we provide constructions to embed another graph as center in both bipartite and k-partite cases. Since any graph is a k-partite graph, for some k, these constructions can be applied in general

8

Distance defined by spanning trees in graphs

71%

Chartrand G., Nebeský L., Zhang P.

Discussiones Mathematicae Graph Theory

|

2007

|

tom 27

|

nr 3

485-506

EN

For a spanning tree T in a nontrivial connected graph G and for vertices u and v in G, there exists a unique u-v path u = u₀, u₁, u₂,..., uₖ = v in T. A u-v T-path in G is a u- v path u = v₀, v₁,...,vₗ = v in G that is a subsequence of the sequence u = u₀, u₁, u₂,..., uₖ = v. A u-v T-path of minimum length is a u-v T-geodesic in G. The T-distance $d_{G|T}(u,v)$ from u to v in G is the length of a u-v T-geodesic. Let geo(G) and geo(G|T) be the set of geodesics and the set of T-geodesics respectively in G. Necessary and sufficient conditions are established for (1) geo(G) = geo(G|T) and (2) geo(G|T) = geo(G|T*), where T and T* are two spanning trees of G. It is shown for a connected graph G that geo(G|T) = geo(G) for every spanning tree T of G if and only if G is a block graph. For a spanning tree T of a connected graph G, it is also shown that geo(G|T) satisfies seven of the eight axioms of the characterization of geo(G). Furthermore, we study the relationship between the distance d and T-distance $d_{G|T}$ in graphs and present several realization results on parameters and subgraphs defined by these two distances.

9

The strong isometric dimension of finite reflexive graphs

61%

Fitzpatrick S., Nowakowski R.

Discussiones Mathematicae Graph Theory

|

2000

|

tom 20

|

nr 1

23-38

EN

The strong isometric dimension of a reflexive graph is related to its injective hull: both deal with embedding reflexive graphs in the strong product of paths. We give several upper and lower bounds for the strong isometric dimension of general graphs; the exact strong isometric dimension for cycles and hypercubes; and the isometric dimension for trees is found to within a factor of two.

10

The Degree-Diameter Problem for Outerplanar Graphs

61%

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.

11

Altitude, Orthocenter of a Triangle and Triangulation

61%

Coghetto R.

Formalized Mathematics

|

2016

|

tom 24

|

nr 1

27-36

EN

We introduce the altitudes of a triangle (the cevians perpendicular to the opposite sides). Using the generalized Ceva’s Theorem, we prove the existence and uniqueness of the orthocenter of a triangle [7]. Finally, we formalize in Mizar [1] some formulas [2] to calculate distance using triangulation.

12

Eccentric distance sum index for some classes of connected graphs

61%

Bielak H., Broniszewska K.

Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica

|

2017

|

tom 71

|

nr 2

EN

In this paper we show some properties of the eccentric distance sum index which is defined as follows $\xi^{d}(G)=\sum_{v \in V(G)}D(v) \varepsilon(v)$. This index is widely used by chemists and biologists in their researches. We present a lower bound of this index for a new class of graphs.

13

On the role of partial Ricci curvature in the geometry of submanifolds and foliations

51%

Rovenskiĭ V.

Annales Polonici Mathematici

|

1998

|

tom 68

|

nr 1

61-82

EN

Submanifolds and foliations with restrictions on q-Ricci curvature are studied. In §1 we estimate the distance between two compact submanifolds in a space of positive q-Ricci curvature, and give applications to special classes of submanifolds and foliations: k-saddle, totally geodesic, with nonpositive extrinsic q-Ricci curvature. In §2 we generalize a lemma by T. Otsuki on asymptotic vectors of a bilinear form and then estimate from below the radius of an immersed submanifold in a simply connected Riemannian space with nonpositive curvature; moreover, we prove a theorem on nonembedding into a circular cylinder when the ambient space is Euclidean. Corollaries are nonembedding theorems of Riemannian manifolds with nonpositive q-Ricci curvature into a Euclidean space. In §3 a lower estimate of the index of relative nullity of a submanifold with nonpositive extrinsic q-Ricci curvature is proven. Corollaries are extremal theorems for a compact submanifold with the nullity foliation in a Riemannian space of positive curvature. On the way, some results by T. Frankel, K. Kenmotsu and C. Xia, J. Morvan, A. Borisenko, S. Tanno, B. O'Neill, J. Moore, T. Ishihara, H. Jacobowitz, L. Florit, M. Dajczer and L. Rodríguez are generalized.

Ograniczanie wyników

Spanning caterpillars with bounded diameter

Distance-Locally Disconnected Graphs

Connected partition dimensions of graphs

The Steiner Wiener Index of A Graph

Inverse Problem on the Steiner Wiener Index

Closed k-stop distance in graphs

The Median Problem on k-Partite Graphs

Distance defined by spanning trees in graphs

The strong isometric dimension of finite reflexive graphs

The Degree-Diameter Problem for Outerplanar Graphs

Altitude, Orthocenter of a Triangle and Triangulation

Eccentric distance sum index for some classes of connected graphs

On the role of partial Ricci curvature in the geometry of submanifolds and foliations