1,721,001 research outputs found
An Upper Bound for the Ramsey Number of a Cycle of Length Four Versus Wheels
Get PDFFor given graphs G and H, the Ramsey numberR(G,H) is the smallest positive integer n such that every graph F of n vertices satisfies the following property: either F contains G or the complement of F contains H. In this paper, we show that the Ramsey number R(C4,Wm)≤m+⌈m3⌉+1 for m ≥ 6
A General Framework for Coloring Problems: Old Results, New Results, and Open Problems
Get PDFn this survey paper we present a general framework for coloring problems that was introduced in a joint paper which the author presented at WG2003. We show how a number of different types of coloring problems, most of which have been motivated from frequency assignment, fit into this framework. We give a survey of the existing results, mainly based on and strongly biased by joint work of the author with several different groups of coauthors, include some new results, and discuss several open problems for each of the variants
BILANGAN RAMSEY SISI DARI r(P3,Pn)
No full textPada paper ini akan ditunjukkan bahwa bilangan Ramsey sisi dari r(P3,Pn) untuk n = 13, 14, 15 adalah 20, 23, 24. Ditunjukkan pula bahwa r(P3,pn)=r(P3,Pk)+r(P3,P1) dengan n = k+l-1 untuk n ganjil dan k, l genap.
Kata kunci: Bilangan Ramsey sisi, Graph lintasa
Determining Finite Connected Graphs Along the Quadratic Embedding Constants of Paths
Get PDFThe QE constant of a finite connected graph , denoted by
, is by definition the maximum of the quadratic function
associated to the distance matrix on a certain sphere of codimension two. We
prove that the QE constants of paths form a strictly increasing sequence
converging to . Then we formulate the problem of determining all the
graphs satisfying
. The answer is
given for and by exploiting forbidden subgraphs for
and the explicit QE constants of star products of the
complete graphs.Comment: 24 pages, 6 figure
The Uniqueness of Almost Moore Digraphs with Degree 4 And Diameter 2
Get PDFAbstract. It is well known that Moore digraphs of degree d > 1 and diameter k > 1 do not exist. For degrees 2 and 3, it has been shown that for diameter k ≥ 3 there are no almost Moore digraphs, i.e. the diregular digraphs of order one less than the Moore bound. Digraphs with order close to the Moore bound arise in the construction of optimal networks. For diameter 2, it is known that almost Moore digraphs exist for any degree because the line digraphs of complete digraphs are examples of such digraphs. However, it is not known whether these are the only almost Moore digraphs. It is shown that for degree 3, there are no almost Moore digraphs of diameter 2 other than the line digraph of K4. In this paper, we shall consider the almost Moore digraphs of diameter 2 and degree 4. We prove that there is exactly one such digraph, namely the line digraph of K5. Ketunggalan Graf Berarah Hampir Moore dengan Derajat 4 dan Diameter 2Sari. Telah lama diketahui bahwa tidak ada graf berarah Moore dengan derajat d>1 dan diameter k>1. Lebih lanjut, untuk derajat 2 dan 3, telah ditunjukkan bahwa untuk diameter t>3, tidak ada graf berarah Hampir Moore, yakni graf berarah teratur dengan orde satu lebih kecil dari batas Moore. Graf berarah dengan orde mendekati batas Moore digunakan dalam pcngkonstruksian jaringan optimal. Untuk diameter 2, diketahui bahwa graf berarah Hampir Moore ada untuk setiap derajat karena graf berarah garis (line digraph) dari graf komplit adalah salah satu contoh dari graf berarah tersebut. Akan tetapi, belum dapat dibuktikan apakah graf berarah tersebut merupakan satu-satunya contoh dari graf berarah Hampir Moore tadi. Selanjutnya telah ditunjukkan bahwa untuk derajat 3, tidak ada graf berarah Hampir Moore diameter 2 selain graf berarah garis dari K4. Pada makalah ini, kita mengkaji graf berarah Hampir Moore diameter 2 dan derajat 4. Kita buktikan bahwa ada tepat satu graf berarah tersebut, yaitu graf berarah garis dari K5
On (4,2)-digraph Containing a Cycle of Length 2
No full textA diregular digraph is a digraph with the in-degree and out-degree of all vertices is constant. The Moore bound for a diregular digraph of degree d and diameter k is M_{d,k}=l+d+d^2+...+d^k. It is well known that diregular digraphs of order M_{d,k}, degree d>l tnd diameter k>l do not exist . A (d,k) -digraph is a diregular digraph of degree d>1, diameter k>1, and number of vertices one less than the Moore bound. For degrees d=2 and 3,it has been shown that for diameter k >= 3 there are no such (d,k)-digraphs. However for diameter 2, it is known that (d,2)-digraphs do exist for any degree d. The line digraph of K_{d+1} is one example of such (42)-digraphs. Furthermore, the recent study showed that there are three non-isomorphic(2,2)-digraphs and exactly one non-isomorphic (3,2)-digraph. In this paper, we shall study (4,2)-digraphs. We show that if (4,2)-digraph G contains a cycle of length 2 then G must be the line
digraph of a complete digraph K_5
A Classification of Graphs through Quadratic Embedding Constants and Clique Graph Insights
Get PDFThe quadratic embedding constant (QEC) of a graph is a new numeric
invariant, which is defined in terms of the distance matrix and is denoted by
. By observing graph structure of the maximal cliques (clique
graph), we show that a graph with admits a
``cactus-like'' structure. We derive a formula for the quadratic embedding
constant of a graph consisting of two maximal cliques. As an application we
discuss characterization of graphs along the increasing sequence of
, where is the path on vertices. In particular, we
determine graphs satisfying
A note on the size Ramsey numbers for matchings versus cycles
Get PDFsummary:For graphs , , , we write if for every red-blue colouring of the edge set of we have a red copy of or a blue copy of in . The size Ramsey number is the minimum number of edges of a graph such that . Erdős and Faudree proved that for the cycle of length and for matchings , the size Ramsey number . We improve their upper bound for and by showing that for and for
- …
