A construction of geodetic blocks
A construction of large graphs of diameter two and given degree from Abelian lifts of dipoles
For any we construct graphs of degree , diameter , and order , obtained as lifts of dipoles with voltages in cyclic groups. For Cayley Abelian graphs of diameter two a slightly better result of has been known [3] but it applies only to special values of degrees depending on prime powers.
A Constructive Extension of the Characterization on PotentiallyK s , t -Bigraphic Pairs
Let Ks,t be the complete bipartite graph with partite sets of size s and t. Let L1 = ([a1, b1], . . . , [am, bm]) and L2 = ([c1, d1], . . . , [cn, dn]) be two sequences of intervals consisting of nonnegative integers with a1 ≥ a2 ≥ . . . ≥ am and c1 ≥ c2 ≥ . . . ≥ cn. We say that L = (L1; L2) is potentially Ks,t (resp. As,t)-bigraphic if there is a simple bipartite graph G with partite sets X = {x1, . . . , xm} and Y = {y1, . . . , yn} such that ai ≤ dG(xi) ≤ bi for 1 ≤ i ≤ m, ci ≤ dG(yi) ≤ di for...
A deceptive fact about functions
The paper provides a proof of a combinatorial result which pertains to the characterization of the set of equations which are solvable in the composition monoid of all partial functions on an infinite set.
A decomposition algorithm for the oriented adjacency graph of the triangulations of a bordered surface with marked points.
A decomposition of gallai multigraphs
An edge-colored cycle is rainbow if its edges are colored with distinct colors. A Gallai (multi)graph is a simple, complete, edge-colored (multi)graph lacking rainbow triangles. As has been previously shown for Gallai graphs, we show that Gallai multigraphs admit a simple iterative construction. We then use this structure to prove Ramsey-type results within Gallai colorings. Moreover, we show that Gallai multigraphs give rise to a surprising and highly structured decomposition into directed trees...
A Décomposition Theorem on Euclidean Steiner Minimal Trees.
A degree condition for the existence of -factors with prescribed properties.
A deletion game on graphs: “Le Pic Arête".
A density result for random sparse oriented graphs and its relation to a conjecture of Woodall.
A Different Short Proof of Brooks’ Theorem
Lovász gave a short proof of Brooks’ theorem by coloring greedily in a good order. We give a different short proof by reducing to the cubic case.
A Digrapf Approach to the Edge-Reconstruction Conjecture
A digraph equation for homomorphic images.
A direct decomposition of 3-connected planar graphs.
A distance between isomorphism classes of trees
A dual proof of the upper bound conjecture for convex polytopes.
A factor graph based genetic algorithm
We propose a new linkage learning genetic algorithm called the Factor Graph based Genetic Algorithm (FGGA). In the FGGA, a factor graph is used to encode the underlying dependencies between variables of the problem. In order to learn the factor graph from a population of potential solutions, a symmetric non-negative matrix factorization is employed to factorize the matrix of pair-wise dependencies. To show the performance of the FGGA, encouraging experimental results on different separable problems...
A family of nonregular distance monotone graphs
A Family of Path Properties for Graphs.
A Fan-Type Heavy Pair Of Subgraphs For Pancyclicity Of 2-Connected Graphs
Let G be a graph on n vertices and let H be a given graph. We say that G is pancyclic, if it contains cycles of all lengths from 3 up to n, and that it is H-f1-heavy, if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K), dK(u, v) = 2 implies [...] mindG(u),dG(v)≥n+12 . In this paper we prove that every 2-connected K1,3, P5-f1-heavy graph is pancyclic. This result completes the answer to the problem of finding f1-heavy pairs of subgraphs implying pancyclicity...