On pancyclic line graphs
On partially directed geodetic graphs
On potentially -graphic sequences
Let be the graph obtained from by removing the edges set of where is a subgraph of . In this paper, we characterize the potentially and -graphic sequences where is a tree on 5 vertices and 3 leaves.
On problems related to characteristic vertices of graphs
On properties of maximal 1-planar graphs
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.
On radially extremal digraphs
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.
On radially extremal graphs and digraphs, a survey
The paper gives an overview of results for radially minimal, critical, maximal and stable graphs and digraphs.
On Randomly Hamiltonian Graphs.
On rational radii coin representations of the wheel graph
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...
On regular bipartite-preserving supergraphs.
On Regular Bipartite-Preserving Supergraphs. (Short Communication).
On regular factors in regular graphs with small radius.
On Sequential Heuristic Methods for the Maximum Independent Set Problem
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.
On signed majority total domination in graphs
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 .
On some graph-theoretical problems of V. G. Vizing
On some Interconnections Between Combinatorial Optimization and Extremal Graph Theory
On some variations of extremal graph problems
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...
On Sparse Spanners of Weighted Graphs.
On systems of graphs intersecting in paths
On the adjacent eccentric distance sum of graphs
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...