A Markov chain approach to randomly grown graphs.
A matching and a Hamiltonian cycle of the fourth power of a connected graph
The following result is proved: Let be a connected graph of order . Then for every matching in there exists a hamiltonian cycle of such that .
A matrix representation of graphs and its spectrum as a graph invariant.
A Matroid on Hypergraphs, with Applications in Scene Analysis and Geometry.
A Maximal Toroidal Graph which is not a Triangulation.
A maximum degree theorem for diameter-2-critical graphs
A graph is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Let G be a diameter-2-critical graph of order n. Murty and Simon conjectured that the number of edges in G is at most ⌊n 2/4⌋ and that the extremal graphs are the complete bipartite graphs K ⌊n/2⌋,⌊n/2⌉. Fan [Discrete Math. 67 (1987), 235–240] proved the conjecture for n ≤ 24 and for n = 26, while Füredi [J. Graph Theory 16 (1992), 81–98] proved the conjecture for n > n 0 where n 0 is a...
A Maximum Resonant Set of Polyomino Graphs
A polyomino graph P is a connected finite subgraph of the infinite plane grid such that each finite face is surrounded by a regular square of side length one and each edge belongs to at least one square. A dimer covering of P corresponds to a perfect matching. Different dimer coverings can interact via an alternating cycle (or square) with respect to them. A set of disjoint squares of P is a resonant set if P has a perfect matching M so that each one of those squares is M-alternating. In this paper,...
A measure of graph vulnerability: Scattering number.
A Metaheuristic Approach to Solving the Generalized Vertex Cover Problem
AMS Subj. Classification: 90C27, 05C85, 90C59The topic is related to solving the generalized vertex cover problem (GVCP) by genetic algorithm. The problem is NP-hard as a generalization of well-known vertex cover problem which was one of the first problems shown to be NP-hard. The definition of the GVCP and basics of genetic algorithms are described. Details of genetic algorithm and numerical results are presented in [8]. Genetic algorithm obtained high quality solutions in a short period of time.
A Method for Classification of Doubly Resolvable Designs and Its Application
This article presents the principal results of the Ph.D. thesis Investigation and classification of doubly resolvable designs by Stela Zhelezova (Institute of Mathematics and Informatics, BAS), successfully defended at the Specialized Academic Council for Informatics and Mathematical Modeling on 22 February 2010.The resolvability of combinatorial designs is intensively investigated because of its applications. This research focuses on resolvable designs with an additional property - they have resolutions...
A method of constructing the frame of a directed graph
In web search engines, such as Google, the ranking of a particular keyword is determined by mathematical tools, e.g., Pagerank or Hits. However, as the size of the network increases, it becomes increasingly difficult to use keyword ranking to quickly find the information required by an individual user. One reason for this phenomenon is the interference of superfluous information with the link structure. The World Wide Web can be expressed as an enormous directed graph. The purpose of the present...
A metric for graphs
A metric graph satisfying [...] w 4 1 = 1 that cannot be lifted to a curve satisfying [...] dim ( W 4 1 ) = 1
For all integers g ≥ 6 we prove the existence of a metric graph G with [...] w41=1 such that G has Clifford index 2 and there is no tropical modification G′ of G such that there exists a finite harmonic morphism of degree 2 from G′ to a metric graph of genus 1. Those examples show that not all dimension theorems on the space classifying special linear systems for curves have immediate translation to the theory of divisors on metric graphs.
A metric on a system of ordered sets
In [3] a metric on a system of isomorphism classes of ordered sets was defined. In this paper we define another metric on the same system and investigate some of its properties. Our approach is motivated by a problem from practice.
A minimal Set of Generators for the Ring of multisymmetric Functions
The purpose of this article is to give, for any (commutative) ring , an explicit minimal set of generators for the ring of multisymmetric functions as an -algebra. In characteristic zero, i.e. when is a -algebra, a minimal set of generators has been known since the 19th century. A rather small generating set in the general case has also recently been given by Vaccarino but it is not minimal in general. We also give a sharp degree bound on the generators, improving the degree bound previously...
A model theory approach to structural limits
The goal of this paper is to unify two lines in a particular area of graph limits. First, we generalize and provide unified treatment of various graph limit concepts by means of a combination of model theory and analysis. Then, as an example, we generalize limits of bounded degree graphs from subgraph testing to finite model testing.
A modification of the median of a tree
The concept of median of a tree is modified, considering only distances from the terminal vertices instead of distances from all vertices.
A moment sequence in the q-world
The aim of the paper is to present some initial results about a possible generalization of moment sequences to a so-called q-calculus. A characterization of such a q-analogue in terms of appropriate positivity conditions is also investigated. Using the result due to Maserick and Szafraniec, we adapt a classical description of Hausdorff moment sequences in terms of positive definiteness and complete monotonicity to the q-situation. This makes a link between q-positive definiteness and q-complete...
A monotone path in an edge-ordered graph.
A Moore-like bound for graphs of diameter 2 and given degree, obtained as abelian lifts of dipoles.