All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 58 Next

Displaying 1141 – 1160 of 1341

Showing per page

On the strong metric dimension of the strong products of graphs

Dorota Kuziak, Ismael G. Yero, Juan A. Rodríguez-Velázquez (2015)

Open Mathematics

Let G be a connected graph. A vertex w ∈ V.G/ strongly resolves two vertices u,v ∈ V.G/ if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set S of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality of a strong resolving set for G is called the strong metric dimension of G. It is well known that the problem of computing this invariant is NP-hard. In this paper we study...

On the strong parity chromatic number

Július Czap, Stanislav Jendroľ, František Kardoš (2011)

Discussiones Mathematicae Graph Theory

A vertex colouring of a 2-connected plane graph G is a strong parity vertex colouring if for every face f and each colour c, the number of vertices incident with f coloured by c is either zero or odd. Czap et al. in [9] proved that every 2-connected plane graph has a proper strong parity vertex colouring with at most 118 colours. In this paper we improve this upper bound for some classes of plane graphs.

On the structural result on normal plane maps

Tomás Madaras, Andrea Marcinová (2002)

Discussiones Mathematicae Graph Theory

We prove the structural result on normal plane maps, which applies to the vertex distance colouring of plane maps. The vertex distance-t chromatic number of a plane graph G with maximum degree Δ(G) ≤ D, D ≥ 12 is proved to be upper bounded by 6 + [ ( 2 D + 12 ) / ( D - 2 ) ] ( ( D - 1 ) ( t - 1 ) - 1 ) . This improves a recent bound 6 + [ ( 3 D + 3 ) / ( D - 2 ) ] ( ( D - 1 ) t - 1 - 1 ) , D ≥ 8 by Jendrol’ and Skupień, and the upper bound for distance-2 chromatic number.

On the structure of path-like trees

F.A. Muntaner-Batle, Miquel Rius-Font (2008)

Discussiones Mathematicae Graph Theory

We study the structure of path-like trees. In order to do this, we introduce a set of trees that we call expandable trees. In this paper we also generalize the concept of path-like trees and we call such generalization generalized path-like trees. As in the case of path-like trees, generalized path-like trees, have very nice labeling properties.

On the structure of plane graphs of minimum face size 5

Tomás Madaras (2004)

Discussiones Mathematicae Graph Theory

A subgraph of a plane graph is light if the sum of the degrees of the vertices of the subgraph in the graph is small. It is known that a plane graph of minimum face size 5 contains light paths and a light pentagon. In this paper we show that every plane graph of minimum face size 5 contains also a light star K 1 , 3 and we present a structural result concerning the existence of a pair of adjacent faces with degree-bounded vertices.

On the sum of dilations of a set

Antal Balog, George Shakan (2014)

Acta Arithmetica

We show that for any relatively prime integers 1 ≤ p < q and for any finite A ⊂ ℤ one has | p · A + q · A | ≥ ( p + q ) | A | - ( p q ) ( p + q - 3 ) ( p + q ) + 1 .

On the sum of powers of Laplacian eigenvalues of bipartite graphs

Bo Zhou, Aleksandar Ilić (2010)

Czechoslovak Mathematical Journal

For a bipartite graph G and a non-zero real α , we give bounds for the sum of the α th powers of the Laplacian eigenvalues of G using the sum of the squares of degrees, from which lower and upper bounds for the incidence energy, and lower bounds for the Kirchhoff index and the Laplacian Estrada index are deduced.

Currently displaying 1141 – 1160 of 1341