Displaying 61 – 80 of 724

Showing per page

A construction of large graphs of diameter two and given degree from Abelian lifts of dipoles

Dávid Mesežnikov (2012)

Kybernetika

For any d 11 we construct graphs of degree d , diameter 2 , and order 8 25 d 2 + O ( d ) , obtained as lifts of dipoles with voltages in cyclic groups. For Cayley Abelian graphs of diameter two a slightly better result of 9 25 d 2 + O ( d ) has been known [3] but it applies only to special values of degrees d depending on prime powers.

A Constructive Extension of the Characterization on PotentiallyK s , t -Bigraphic Pairs

Ji-Yun Guo, Jian-Hua Yin (2017)

Discussiones Mathematicae Graph Theory

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

Wiesław Dziobiak, Andrzej Ehrenfeucht, Jacqueline Grace, Donald Silberger (2000)

Fundamenta Mathematicae

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 of gallai multigraphs

Alexander Halperin, Colton Magnant, Kyle Pula (2014)

Discussiones Mathematicae Graph Theory

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 Different Short Proof of Brooks’ Theorem

Landon Rabern (2014)

Discussiones Mathematicae Graph Theory

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 factor graph based genetic algorithm

B. Hoda Helmi, Adel T. Rahmani, Martin Pelikan (2014)

International Journal of Applied Mathematics and Computer Science

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 Fan-Type Heavy Pair Of Subgraphs For Pancyclicity Of 2-Connected Graphs

Wojciech Wideł (2016)

Discussiones Mathematicae Graph Theory

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 [...] min⁡dG(u),dG(v)≥n+12 min { d G ( u ) , d G ( v ) } n + 1 2 . 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...

Currently displaying 61 – 80 of 724