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 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 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 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.
A multilevel algorithm for force-directed graph-drawing.
A multipartite version of the Turan problem - density conditions and eigenvalues.
A multivariate Lagrange inversion formula for asymptotic calculations.
A necessary and sufficient eigenvector condition for a connected graph to be bipartite.
A Neighborhood Condition for Fractional ID-[A, B]-Factor-Critical Graphs
Let G be a graph of order n, and let a and b be two integers with 1 ≤ a ≤ b. Let h : E(G) → [0, 1] be a function. If a ≤ ∑e∋x h(e) ≤ b holds for any x ∈ V (G), then we call G[Fh] a fractional [a, b]-factor of G with indicator function h, where Fh = {e ∈ E(G) : h(e) > 0}. A graph G is fractional independent-set-deletable [a, b]-factor-critical (in short, fractional ID-[a, b]- factor-critical) if G − I has a fractional [a, b]-factor for every independent set I of G. In this paper, it is proved...
A new approach to chordal graphs
By a chordal graph is meant a graph with no induced cycle of length . By a ternary system is meant an ordered pair , where is a finite nonempty set, and . Ternary systems satisfying certain axioms (A1)–(A5) are studied in this paper; note that these axioms can be formulated in a language of the first-order logic. For every finite nonempty set , a bijective mapping from the set of all connected chordal graphs with onto the set of all ternary systems satisfying the axioms (A1)–(A5) is...