Page 1 Next

Displaying 1 – 20 of 123

Showing per page

L(2, 1)-Labelings of Some Families of Oriented Planar Graphs

Sagnik Sen (2014)

Discussiones Mathematicae Graph Theory

In this paper we determine, or give lower and upper bounds on, the 2-dipath and oriented L(2, 1)-span of the family of planar graphs, planar graphs with girth 5, 11, 16, partial k-trees, outerplanar graphs and cacti.

Labeled shortest paths in digraphs with negative and positive edge weights

Phillip G. Bradford, David A. Thomas (2009)

RAIRO - Theoretical Informatics and Applications

This paper gives a shortest path algorithm for CFG (context free grammar) labeled and weighted digraphs where edge weights may be positive or negative, but negative-weight cycles are not allowed in the underlying unlabeled graph. These results build directly on an algorithm of Barrett et al. [SIAM J. Comput.30 (2000) 809–837]. In addition to many other results, they gave a shortest path algorithm for CFG labeled and weighted digraphs where all edges are nonnegative. Our algorithm is based closely...

Labeling the vertex amalgamation of graphs

Ramon M. Figueroa-Centeno, Rikio Ichishima, Francesc A. Muntaner-Batle (2003)

Discussiones Mathematicae Graph Theory

A graph G of size q is graceful if there exists an injective function f:V(G)→ 0,1,...,q such that each edge uv of G is labeled |f(u)-f(v)| and the resulting edge labels are distinct. Also, a (p,q) graph G with q ≥ p is harmonious if there exists an injective function f : V ( G ) Z q such that each edge uv of G is labeled f(u) + f(v) mod q and the resulting edge labels are distinct, whereas G is felicitous if there exists an injective function f : V ( G ) Z q + 1 such that each edge uv of G is labeled f(u) + f(v) mod q and the...

Lack of Gromov-hyperbolicity in small-world networks

Yilun Shang (2012)

Open Mathematics

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...

Large Degree Vertices in Longest Cycles of Graphs, I

Binlong Li, Liming Xiong, Jun Yin (2016)

Discussiones Mathematicae Graph Theory

In this paper, we consider the least integer d such that every longest cycle of a k-connected graph of order n (and of independent number α) contains all vertices of degree at least d.

Currently displaying 1 – 20 of 123

Page 1 Next