Combinatorics and Graph Theory

1409 Submissions

[3] viXra:1409.0165 [pdf] submitted on 2014-09-24 01:48:20

Advances in Graph Algorithms

Authors: Ton Kloks, Yue-Li Wang
Comments: 172 Pages. This is the text of a course on various techniques applied in algorithmic graph theory.

This is a course on advances in graph algorithms that we taught in Taiwan. The topics included are Exact algorithms, Graph classes, fixed-parameter algorithms, and graph decompositions.
Category: Combinatorics and Graph Theory

[2] viXra:1409.0162 [pdf] submitted on 2014-09-23 09:26:39

The Proof for Non-existence of Magic Square of Squares in Order Three

Authors: Bambore Dawit
Comments: 9 Pages. we need to follow instruction in each step for detail calculations

This paper shows the non-existence of magic square of squares in order three by investigating two new tools, the first is representing three perfect squares in arithmetic progression by two numbers and the second is realizing the impossibility of two similar equations for the same problem at the same time in different ways and the variables of one is relatively less than the other.
Category: Combinatorics and Graph Theory

[1] viXra:1409.0113 [pdf] submitted on 2014-09-14 08:55:20

The Chromatic-Covering of a Graph: Ratios, Domination, Areas and Farey Sequences

Authors: Paul August Winter
Comments: 21 Pages.

The study of the chromatic number and vertex coverings of graphs has opened many avenues of research. In this paper we combine these two concepts in a ratio, to investigate the domination effect of the chromatic number, of the subgaph induced by a vertex covering of a graph G (called the cover graph of G), on the original chromatic number of G, where large number of vertices are involved. This is referred to as the chromatic-cover domination. If this chromatic-cover ratio is a function of n, the order of graphs belonging to a class of graph, then we discuss its horizontal asymptotic behavior and attach the graphs average degree to the Riemann integral of this ratio, thus associating chromatic-cover area with classes of graphs. We found that the chromatic-cover domination had a strongest effect on complete graph, while this chromatic-cover domination had zero effect on star graphs. We show that the chromatic-cover asymptote of all classes of graphs belong to the interval [0,1], and conjecture that complete graphs are the only class of graphs having chromatic-cover asymptote of 1 and that they also have the largest area . We construct a class of graphs, using known classes of graph where vertices are replaced with cliques on q vertices, thus generating sequences which converges to the chromatic-cover asymptote of known classes of graphs. We use a particular sequence to construct a Farey chromatic-cover sequence which is a subsequence of the famous Farey sequence.
Category: Combinatorics and Graph Theory