Minimum semidefinite rank of outerplanar graphs and the tree cover number.
Minimum Steiner Trees in Normed Planes.
Minimum vertex ranking spanning tree problem for chordal and proper interval graphs
A vertex k-ranking of a simple graph is a coloring of its vertices with k colors in such a way that each path connecting two vertices of the same color contains a vertex with a bigger color. Consider the minimum vertex ranking spanning tree (MVRST) problem where the goal is to find a spanning tree of a given graph G which has a vertex ranking using the minimal number of colors over vertex rankings of all spanning trees of G. K. Miyata et al. proved in [NP-hardness proof and an approximation algorithm...
Minimum-area drawings of plane 3-trees.
Minmax strongly connected subgraphs with node penalties.
Minus total domination in graphs
A three-valued function defined on the vertices of a graph is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. That is, for every , , where consists of every vertex adjacent to . The weight of an MTDF is , over all vertices . The minus total domination number of a graph , denoted , equals the minimum weight of an MTDF of . In this paper, we discuss some properties of minus total domination on a graph and obtain...
Mixing time for a random walk on rooted trees.
Modèles d'optimisation en analyse des données relationnelles
Model-interpretability into trees and applications.
Moderate deviations in a random graph and for the spectrum of Bernoulli random matrices.
Moderní pohled na „jistý problém minimální‟
Modified Wiener indices of thorn trees
Modular and median signpost systems and their underlying graphs
The concept of a signpost system on a set is introduced. It is a ternary relation on the set satisfying three fairly natural axioms. Its underlying graph is introduced. When the underlying graph is disconnected some unexpected things may happen. The main focus are signpost systems satisfying some extra axioms. Their underlying graphs have lots of structure: the components are modular graphs or median graphs. Yet another axiom guarantees that the underlying graph is also connected. The main results...
Modular, -noncrossing diagrams.
Moessnerian theorems. How to prove them by simple graph theoretical inspection.
Monochromatic cycles and monochromatic paths in arc-colored digraphs
We call the digraph D an m-colored digraph if the arcs of D are colored with m colors. A path (or a cycle) is called monochromatic if all of its arcs are colored alike. A cycle is called a quasi-monochromatic cycle if with at most one exception all of its arcs are colored alike. A subdigraph H in D is called rainbow if all its arcs have different colors. A set N ⊆ V(D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different vertices...
Monochromatic kernel-perfectness of special classes of digraphs
In this paper, we introduce the concept of monochromatic kernel-perfect digraph, and we prove the following two results: (1) If D is a digraph without monochromatic directed cycles, then D and each are monochromatic kernel-perfect digraphs if and only if the composition over D of is a monochromatic kernel-perfect digraph. (2) D is a monochromatic kernel-perfect digraph if and only if for any B ⊆ V(D), the duplication of D over B, , is a monochromatic kernel-perfect digraph.
Monochromatic paths and monochromatic sets of arcs in 3-quasitransitive digraphs
We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours. A directed path is called monochromatic if all of its arcs are coloured alike. A set N of vertices of D is called a kernel by monochromatic paths if for every pair of vertices of N there is no monochromatic path between them and for every vertex v ∉ N there is a monochromatic path from v to N. We denote by A⁺(u) the set of arcs of D that have u as the initial vertex. We prove that if D is an m-coloured 3-quasitransitive...
Monochromatic paths and monochromatic sets of arcs in bipartite tournaments
We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours and all of them are used. A directed path is called monochromatic if all of its arcs are coloured alike. A set N of vertices of D is called a kernel by monochromatic paths if for every pair of vertices there is no monochromatic path between them and for every vertex v in V(D)∖N there is a monochromatic path from v to some vertex in N. We denote by A⁺(u) the set of arcs of D that have u as the initial...
Monochromatic paths and monochromatic sets of arcs in quasi-transitive digraphs
Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively. We call the digraph D an m-coloured digraph if each arc of D is coloured by an element of {1,2,...,m} where m ≥ 1. A directed path is called monochromatic if all of its arcs are coloured alike. A set N of vertices of D is called a kernel by monochromatic paths if there is no monochromatic path between two vertices of N and if for every vertex v not in N there is a monochromatic path from v to some vertex...