A graph is called 1-planar if there exists a drawing in the plane so that each edge contains at most one crossing. We study maximal 1-planar graphs from the point of view of properties of their diagrams, local structure and hamiltonicity.
We define digraphs minimal, critical, and maximal by three types of radii. Some of these classes are completely characterized, while for the others it is shown that they are large in terms of induced subgraphs.
The paper gives an overview of results for radially minimal, critical, maximal and stable graphs and digraphs.
A flower is a coin graph representation of the wheel graph. A petal of a flower is an outer coin connected to the center coin. The results of this paper are twofold. First we derive a parametrization of all the rational (and hence integer) radii coins of the 3-petal flower, also known as Apollonian circles or Soddy circles. Secondly we consider a general n-petal flower and show there is a unique irreducible polynomial Pₙ in n variables over the rationals ℚ, the affine variety of which contains the...
We consider sequential heuristics methods for the Maximum Independent Set (MIS) problem. Three classical algorithms, VO [11], MIN [12], or MAX [6] , are revisited. We combine Algorithm MIN with the α-redundant vertex technique[3]. Induced forbidden subgraph sets, under which the algorithms give maximum independent sets, are described. The Caro-Wei bound [4,14] is verified and performance of the algorithms on some special graphs is considered.
We initiate the study of signed majority total domination in graphs. Let be a simple graph. For any real valued function and , let . A signed majority total dominating function is a function such that for at least a half of the vertices . The signed majority total domination number of a graph is is a signed majority total dominating function on . We research some properties of the signed majority total domination number of a graph and obtain a few lower bounds of .
A set P of graphs is termed hereditary property if and only if it contains all subgraphs of any graph G belonging to P. A graph is said to be maximal with respect to a hereditary property P (shortly P-maximal) whenever it belongs to P and none of its proper supergraphs of the same order has the property P. A graph is P-extremal if it has a the maximum number of edges among all P-maximal graphs of given order. The number of its edges is denoted by ex(n, P). If the number of edges of a P-maximal...
In this paper we show bounds for the adjacent eccentric distance sum of graphs in terms of Wiener index, maximum degree and minimum degree. We extend some earlier results of Hua and Yu [Bounds for the Adjacent Eccentric Distance Sum, International Mathematical Forum. Vol. 7 (2O02) no. 26. 1280-1294]. The adjaceni eccentric distance sum index of the graph G is defined as [...] where ε(υ) is the eccentricity of the vertex υ, deg(υ) is the degree of the vertex υ and D(υ) = ∑u∊v(G) d (u,υ)is the sum...
The investigation of the counting function of the set of integral elements, in an algebraic number field, with factorizations of at most k different lengths gives rise to a combinatorial constant depending only on the class group of the number field and the integer k. In this paper the value of these constants, in case the class group is an elementary p-group, is estimated, and determined under additional conditions. In particular, it is proved that for elementary 2-groups these constants are equivalent...