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

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

The Degree-Diameter Problem for Outerplanar Graphs

100%
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.
2
Content available remote

On the Laplacian Coefficients of Tricyclic Graphs with Prescribed Matching Number

100%
Luo J., Zhu Z., Wan R.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
505-522
EN
Let [...] φ(L(G))=det (xI−L(G))=∑k=0n(−1)kck(G)xn−k $\phi (L(G)) = \det (xI - L(G)) = \sum\nolimits_{k = 0}^n {( - 1)^k c_k (G)x^{n - k} } $ be the Laplacian characteristic polynomial of G. In this paper, we characterize the minimal graphs with the minimum Laplacian coefficients in 𝒢n,n+2(i) (the set of all tricyclic graphs with fixed order n and matching number i). Furthermore, the graphs with the minimal Laplacian-like energy, which is the sum of square roots of all roots on ϕ(L(G)), is also determined in 𝒢n,n+2(i).
3
Content available remote

Weak Total Resolvability In Graphs

100%
Casel K., Estrada-Moreno A., Fernau H., Rodríguez-Velázquez J. A.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
185-210
EN
A vertex v ∈ V (G) is said to distinguish two vertices x, y ∈ V (G) of a graph G if the distance from v to x is di erent from the distance from v to y. A set W ⊆ V (G) is a total resolving set for a graph G if for every pair of vertices x, y ∈ V (G), there exists some vertex w ∈ W − {x, y} which distinguishes x and y, while W is a weak total resolving set if for every x ∈ V (G)−W and y ∈ W, there exists some w ∈ W −{y} which distinguishes x and y. A weak total resolving set of minimum cardinality is called a weak total metric basis of G and its cardinality the weak total metric dimension of G. Our main contributions are the following ones: (a) Graphs with small and large weak total metric bases are characterised. (b) We explore the (tight) relation to independent 2-domination. (c) We introduce a new graph parameter, called weak total adjacency dimension and present results that are analogous to those presented for weak total dimension. (d) For trees, we derive a characterisation of the weak total (adjacency) metric dimension. Also, exact figures for our parameters are presented for (generalised) fans and wheels. (e) We show that for Cartesian product graphs, the weak total (adjacency) metric dimension is usually pretty small. (f) The weak total (adjacency) dimension is studied for lexicographic products of graphs.
4
Content available remote

Computing the Metric Dimension of a Graph from Primary Subgraphs

100%
Kuziak D., Rodríguez-Velázquez J. A., Yero I. G.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
273-293
EN
Let G be a connected graph. Given an ordered set W = {w1, . . . , wk} ⊆ V (G) and a vertex u ∈ V (G), the representation of u with respect to W is the ordered k-tuple (d(u, w1), d(u, w2), . . . , d(u, wk)), where d(u, wi) denotes the distance between u and wi. The set W is a metric generator for G if every two different vertices of G have distinct representations. A minimum cardinality metric generator is called a metric basis of G and its cardinality is called the metric dimension of G. It is well known that the problem of finding the metric dimension of a graph is NP-hard. In this paper we obtain closed formulae for the metric dimension of graphs with cut vertices. The main results are applied to specific constructions including rooted product graphs, corona product graphs, block graphs and chains of graphs.
5
Content available remote

A Characterization for 2-Self-Centered Graphs

100%
Shekarriz M. H., Mirzavaziri M., Mirzavaziri K.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
27-37
EN
A graph is called 2-self-centered if its diameter and radius both equal to 2. In this paper, we begin characterizing these graphs by characterizing edge-maximal 2-self-centered graphs via their complements. Then we split characterizing edge-minimal 2-self-centered graphs into two cases. First, we characterize edge-minimal 2-self-centered graphs without triangles by introducing specialized bi-independent covering (SBIC) and a structure named generalized complete bipartite graph (GCBG). Then, we complete characterization by characterizing edge-minimal 2-self-centered graphs with some triangles. Hence, the main characterization is done since a graph is 2-self-centered if and only if it is a spanning subgraph of some edge-maximal 2-self-centered graphs and, at the same time, it is a spanning supergraph of some edge-minimal 2-self-centered graphs.
6
Content available remote

Strong edge geodetic problem in networks

100%
Manuel P., Klavžar S., Xavier A., Arokiaraj A., Thomas E.
Open Mathematics
|
2017
|
tom 15
|
nr 1
1225-1235
EN
Geodesic covering problems form a widely researched topic in graph theory. One such problem is geodetic problem introduced by Harary et al. [Math. Comput. Modelling, 1993, 17, 89-95]. Here we introduce a variation of the geodetic problem and call it strong edge geodetic problem. We illustrate how this problem is evolved from social transport networks. It is shown that the strong edge geodetic problem is NP-complete. We derive lower and upper bounds for the strong edge geodetic number and demonstrate that these bounds are sharp. We produce exact solutions for trees, block graphs, silicate networks and glued binary trees without randomization.
7
Content available remote

A Note on the Interval Function of a Disconnected Graph

76%
Changat M., Hossein Nezhad F., Mulder H. M., Narayanan N.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
39-48
EN
In this note we extend the Mulder-Nebeský characterization of the interval function of a connected graph to the disconnected case. One axiom needs to be adapted, but also a new axiom is needed in addition.
8
Content available remote

Inverse Problem on the Steiner Wiener Index

76%
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

Lack of Gromov-hyperbolicity in small-world networks

76%
Shang Y.
Open Mathematics
|
2012
|
tom 10
|
nr 3
1152-1158
EN
The geometry of complex networks is closely related with their structure and function. In this paper, we investigate the Gromov-hyperbolicity of the Newman-Watts model of small-world networks. It is known that asymptotic Erdős-Rényi random graphs are not hyperbolic. We show that the Newman-Watts ones built on top of them by adding lattice-induced clustering are not hyperbolic as the network size goes to infinity. Numerical simulations are provided to illustrate the effects of various parameters on hyperbolicity in this model.
10
Content available remote

The hyperbolicity constant of infinite circulant graphs

76%
Rodríguez J. M., Sigarreta J. M.
Open Mathematics
|
2017
|
tom 15
|
nr 1
800-814
EN
If X is a geodesic metric space and x1, x2, x3 ∈ X, a geodesic triangle T = {x1, x2, x3} is the union of the three geodesics [x1x2], [x2x3] and [x3x1] in X. The space X is δ-hyperbolic (in the Gromov sense) if any side of T is contained in a δ-neighborhood of the union of the two other sides, for every geodesic triangle T in X. Deciding whether or not a graph is hyperbolic is usually very difficult; therefore, it is interesting to find classes of graphs which are hyperbolic. A graph is circulant if it has a cyclic group of automorphisms that includes an automorphism taking any vertex to any other vertex. In this paper we prove that infinite circulant graphs and their complements are hyperbolic. Furthermore, we obtain several sharp inequalities for the hyperbolicity constant of a large class of infinite circulant graphs and the precise value of the hyperbolicity constant of many circulant graphs. Besides, we give sharp bounds for the hyperbolicity constant of the complement of every infinite circulant graph.
11
Content available remote

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

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