Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 34–47

https://produccioncientificaluz.org/index.php/divulgaciones/

DOI: https://doi.org/10.5281/zenodo.7487440

(CC BY-NC-SA 4.0)

Autor(es)

e-ISSN 2731-2437

p-ISSN 1315-2068

Matriz de adyacencia de Ramsey del grafo

KR(G,H)con componentes h-buenas y las

relaciones geom´etricas entre lados y v´ertices de

los grafos G,HyKR(G,H)

Ramsey adjacency matrix of the graph KR(G,H)with h-good components and the

geometric relationship that exists between sides and vertices of the graphs G,H

and KR(G,H).

Jos´e Figueroa (jose3765@gmail.com)

Departamento de Qu´ımica

Universidad Clodosbaldo Russi´an

Cuman´a, Rep´ublica Bolivariana de Venezuela.

Felicia Villarroel (feliciavillarroel@gmail.com)

Departamento de Matem´atica

Universidad de Oriente

Cuman´a, Rep´ublica Bolivariana de Venezuela.

Henry Ram´ırez (hlramirez6@hotmail.com)

Departamento de Higiene y Seguridad Laboral

Universidad Clodosbaldo Russi´an

Cuman´a, Rep´ublica Bolivariana de Venezuela.

Tob´ıas Rosas (tjrosas@gmail.com)

ORCID: https://orcid.org/0000-0002-8085-5011

Departamento de Matem´atica, Facultad Experimental de Ciencias

Universidad del Zulia

Maracaibo, Rep´ublica Bolivariana de Venezuela.

Resumen

Sean GyHdos grafos simples, ﬁnitos, y no vac´ıos. El n´umero de Ramsey R(G, H), se

deﬁne como el menor entero positivo n, tal que hay un grafo Fde orden nque contiene un

subgrafo G0copia monocrom´atica isomorfa a G, o el complemento de F(denotado por F)

contiene un subgrafo H0copia monocrom´atica isomorfa a H. Se dice que el grafo completo Kn

contiene componentes h-buena, si para toda secuencia si, con i= 1,· · · , m + 1, donde mes la

talla de cada secuencia que colorean los lados del grafo completo Kn=F∪F, tal que se pueda

extraer de F, al menos una copia monocrom´atica G

0isomorfa a G, o Fcontenga al menos

una copia monocrom´atica H

0isomorfa a H. En este manuscrito se presentan dos resultados

principales, a saber: 1) Se determinan los lados incidentes de cada v´ertices v1,...,vndel grafo

Recibido 10/09/2021. Revisado 20/10/2021. Aceptado 15/06/2022.

MSC (2010): Primary 05C55; Secondary 05C15.

Autor de correspondencia: Jos´e Figueroa

Matriz de adyacencia Ramsey 35

Gde orden n, a trav´es de su matriz de adyacencia A(G), obteniendo la f´ormula T raz(M) =

i=1 d(vi) = 2|E(G)|, donde M= (A(G))2es una matriz de orden n×n,T raz(M) es la

traza de la matriz M, y d(vi) es el grado del v´ertice vipara i= 1,...,n. 2) Se determina la

matriz de adyacencia Ramsey del menor grafo completo KR(G,H)con componentes h-buena.

Se determina a trav´es de los elementos mij de M, las relaciones existentes entre los lados

y los v´ertices de los grafos GyH, con respecto a KR(G,H)y se obtuvieron las siguientes

propiedades:

1) X

i>j

mij =X

i<j

mij =mij |E(KR(G,H))|=k|E(KR(G,H))|, con k=mij ∈M.

2) Existen r, s ∈Z+, dependientes de E(G), E(H) y E(KR(G,H)), tal que E(KR(G,H))

E(G)

3) Existen p, q ∈Z+, dependientes de V(G), V(H) y V(KR(G,H)), tal que, V(KR(G,H))

V(H)

4) T raz(M) =

i=1

d(vi) = 2|E(Kn)|.

Palabras y frases clave: Teor´ıa Combinatoria, N´umeros de Ramsey, Grafos con com-

ponentes h-buena, Matriz de adyacencia, Producto de Matrices, Matriz diagonal, Matrices

triangulares.

Abstract

Let be Gand Htwo simple graphs, ﬁnite and non-empty. The Ramsey R(G, H) number,

is deﬁned as the smallest positive integer n, such that there is a graph F, that contains

a monochrome copy G

0isomorphic to Gor the complement of F(denote by F), contains

a monochrome copy H

0isomorphic to H. It is said that the complete graph Kncontains

components h-good, if for every sequence siof size m, with i= 1,· · · , m + 1, that colors

the sides of the complete graph Kn=F∪F, such that can be extracted from F, at least

one G

0monochrome copy isomorphic to G´or Fcontains at least one H

0monochrome copy

isomorphic to H. Two main results are presented in this manuscript, these are: 1) The

incident sides of each vertex v1,...,vnof the graph Gare determined, through an adjacency

matrix A(G), getting the formula T raz(M) = Pn

i=1 d(vi) = 2|E(G)|, where M= (A(G))2

is a square matrix of order n×n,T raz(M) is the trace of the matrix M, and d(vi) is the

degree of the vifor i= 1,...,n. 2) The Ramsey adjacency matrix of the least complete graph

KR(G,H)with components h-good is determined. It is determined through the elements mij

of M, the relationships between the sides and the vertices of the graphs Gand H, with

respect to KR(G,H)and the following properties were obtained:

1) X

i>j

mij =X

i<j

mij =mij |E(Kn)|=k|E(Kn)|, with k=mij ∈M.

2) There exist r, s ∈Z+, dependent on E(G), E(H) and E(KR(G,H)), such that E(Kn)

E(G)

3) There exist p, q ∈Z+, dependent on V(G), V(H) and V(KR(G,H)), such that V(KR(G,H))

V(H)

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 34–47

36 Jos´e Figueroa - Felicia Villarroel - Henry Ram´ırez - Tob´ıas Rosas

4) T raz(M) =

i=1

d(vi) = 2|E(KR(G,H))|.

Key words and phrases: Combinatorial Theory, Ramsey Numbers, Graph with com-

ponents h-good, Adjacency Matrix, Product of Matrices, Diagonal Matrix, Triangular Ma-

trices.

1 Introducci´on

En este trabajo se consideran todos los grafos simples, ﬁnitos, sin lazos y no vac´ıos. En [1] Diestel,

expresa que un grafo G, es un par de conjuntos (V(G), E(G)), denotado por G:= (V(G), E(G)),

donde V(G) es un conjunto no vac´ıo de elementos llamados v´ertices onodos yE(G) es un conjunto

de pares no ordenados de elementos de V, llamados lados oaristas. Si Ges un grafo que no posee

lazos ni lados m´ultiples, entonces Gse dice grafo simple. Los vecinos de un v´ertice u∈V(G),

denotado por NG(u), es el conjunto de todos los v´ertices v∈V(G) tal que (u, v)∈E(G). El orden

de G, denotado por |G|, es el n´umero de v´ertices de G. Dado un grafo simple F, su complemento

ser´a denotado por F, y adem´as se tiene que el grafo completo Kn=F∪F. En [2] Figueroa,

se dice que el grafo completo Kncontiene componentes h-buena, si para toda secuencia si, con

i= 1,· · · , m + 1, donde mes el tama˜no de cada secuencia que colorea los lados del grafo completo

Kn=F∪F, tales que pueda extraer de F, al menos una copia monocrom´atica G0isomorfa a Go

extraer de Fal menos una copia monocrom´atica H0isomorfa a H. En [3] Grassmann y Tremblay,

deﬁnen la matriz de adyacencia A(G) de un grafo Gcon nv´ertices, v1, . . . , vn, como una matriz

cuadrada sim´etrica de orden n×ncuyos elementos ai,j se deﬁnen de la siguiente manera:

ai,j (G) = 1 si (vi, vj)∈E(G)

0 si (vi, vj)/∈E(G),

Una matriz cuadrada M= [mij ]n

i,j=1, de orden n, se dice sim´etrica si mij =mji, para todo

i, j ∈ {1, . . . , n}, es decir, M=Mt(la transpuesta de la matriz). Adem´as, Mse denomina

diagonal si mij = 0 si i6=j,∀i, j ∈ {1,2,· · · , n}. Se denotar´a por T raz(M) a la traza de la

matriz M.

N´otese que de una matriz cuadrada M= [mij ]n

i,j=1, de orden n, se puede obtener una matriz

diagonal Diag(M) deﬁnida por Diag(M)=[mij ×δij ]n

i,j=1, con

δij =0 si i6=j

1 si i=j

Diag(M)=[mi,j ×δij ]n

i,j=1 =







m11 0 0 · · · 0

0m22 0· · · 0

0 0 m33

. 0

000...0

000.

.mnn







de manera que T raz(M) = T raz(Diag(M)) =

i=1

mii.

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 34–47

Matriz de adyacencia Ramsey 37

2 Grados de los v´ertices de un grafo G, a trav´es de su

matriz de adyacencia.

Se dar´an a continuaci´on algunos ejemplos ilustrativos donde se reﬂeja parte de los resultados de

esta secci´on.

Ejemplo 2.1. Sea Gel grafo diamante como se observa en la Figura 1.

Figura 1: K4−l, grafo diamante

Sea la matriz de adyacencia A(G)del grafo diamante G, donde A(G)es una matrices sim´etri-

ca, ya que cada lado del grafo Gse cuenta dos veces en G.

A(G) = 





0 1 1 1

1 0 1 0

1 1 0 1

1 0 1 0







Luego, deﬁniendo la matriz M= (A(G))2por

M=





0 1 1 1

1 0 1 0

1 1 0 1

1 0 1 0







×





0 1 1 1

1 0 1 0

1 1 0 1

1 0 1 0







=





3 1 2 1

1 2 1 2

2 1 3 1

1 2 1 2







N´otese que Mes una matriz sim´etrica, ya que el producto de matrices sim´etricas es un matriz

sim´etrica.

Luego, calculando la matriz diagonal Diag(M), se tiene que

Diag(M)=[mij ×δi,j ]4

i,j=1 =





3000

0200

0030

0002







T raz(M) =

i=1

mii =

i=1

d(vi) = 3 + 2 + 3 + 2 = 10 = 2 ×5 = 2|E(G)|.

Ejemplo 2.2. Sea Gel grafo pez como se observa en la Figura 2.

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 34–47

38 Jos´e Figueroa - Felicia Villarroel - Henry Ram´ırez - Tob´ıas Rosas

Figura 2: Grafo pez

Sea la matriz de adyacencia A(G)del grafo pez G.

A(G) =







0 1 0 0 0 1

1 0 1 0 1 1

0 1 0 1 0 0

0 0 1 0 1 0

0 1 0 1 0 0

1 1 0 0 0 0







Luego, deﬁniendo la matriz M= (A(G))2por







0 1 0 0 0 1

1 0 1 0 1 1

0 1 0 1 0 0

0 0 1 0 1 0

0 1 0 1 0 0

1 1 0 0 0 0













0 1 0 0 0 1

1 0 1 0 1 1

0 1 0 1 0 0

0 0 1 0 1 0

0 1 0 1 0 0

1 1 0 0 0 0













2 1 1 0 1 1

1 4 0 2 0 1

1 0 2 0 2 1

0 2 0 2 0 0

1 0 2 0 2 1

1 1 1 0 1 2







Observe que M, es una matriz sim´etrica en el sentido usual. Entonces,

Diag(M) = [mij ×δi,j ]6

i,j=1 =







200000

040000

002000

000200

000020

000002







T raz(M) =

i=1

mii =

i=1

d(vi) = 2 + 4 + 2 + 2 + 2 + 2 = 14 = 2 ×7=2|E(G)|.

Ejemplo 2.3. Sea Gel grafo ´arbol como se observa en la Figura 3.

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 34–47

Matriz de adyacencia Ramsey 39

Figura 3: Grafo ´arbol.

Sea la matriz de adyacencia A(G)del grafo ´arbol.

A(G) =







0001000000000

1110000000001

0000001000000

0000110000001

0000000000010

0000000111101

0001001000010







Sea M= (A(G))2. As´ı, la matriz Mes una matriz sim´etrica y su diagonal est´a dada por.

Diag(M)=[mij ×δi,j ]13

i,j=1 =







1000000000000

0100000000000

0010000000000

0004000000000

0000100000000

0000010000000

0000003000000

0000000100000

0000000010000

0000000001000

0000000000100

0000000000050

0000000000003







T raz(M) = T raz [mij ×δi,j ]13

i,j=1=

i=1

mii =

i=1

d(vi) = 24 = 2 ×12 = 2|E(G)|.

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 34–47

40 Jos´e Figueroa - Felicia Villarroel - Henry Ram´ırez - Tob´ıas Rosas

Teorema 2.1. Sea A(G)la matriz de adyacencia de un grafo simple Gcualesquiera, ﬁnito y sin

lazos. Sea M= (A(G))2, con Diag(M)=[mij ×δi,j ]n

i,j=1, entonces

T raz(M) = T raz [mij ×δi,j ]n

i,j=1=

i=1

d(vi)=2|E(G)|.

Demostraci´on. Sea A(G) la matriz de adyacencia de un grafo simple cualquiera G, sin lazos. Como

A(G) es una matriz sim´etrica, entonces aij =aji para todo i, j ∈ {1, . . . , n}. Luego, considere

M= (A(G))2la cual es tambi´en una matriz sim´etrica, porque el producto de matrices sim´etricas

es sim´etrica. N´otese que, por deﬁnici´on de M, el elemento mii est´a dado por la expresi´on

i1+a2

i2+· · · +a2

in (2.1)

para todo i= 1, . . . , n. Como los elementos o entradas de la matriz A(G) son 0 y 1 se tiene que

la expresi´on en (2.1) se transforma en

ai1+ai2+· · · +ain (2.2)

Por otro lado, obs´ervese que la suma de las entradas de la ﬁla i-´esima de la matriz A(G) da como

resultado el n´umero de v´ertices de V(G) relacionados con el v´ertice vi, es decir,

d(vi) = ai1+ai2+· · · +ain (2.3)

Ahora, sea δij el delta de Kronecker y considerando la matriz M= [mij ]n

i,j=1, se puede obtener

la matriz diagonal Diag(M)=[mij ×δi,j ]n

i,j=1. As´ı, por las ecuaciones (2.2) y (2.3), se tiene que

T raz(M)=(a11 +· · · +a1n) + · · · + (an1+· · · +ann)

=d(v1) + · · · +d(vn)

= 2|E(G)|

Por lo tanto,

T raz(M) =

i=1

d(vi) = 2|E(G)|.

3 Matriz de adyacencia Ramsey A(KR(G,H)), y la relaci´on

existente entre los lados y v´ertices de los grafos G,Hy

KR(G,H).

Deﬁnici´on 3.1. Sean GyHdos grafos simples cualesquiera, ﬁnitos y sin lazos. Se llama matriz

de adyacencia Ramsey, denotada por A(KR(G,H)), a la matriz de adyacencia del menor grafo

completo KR(G,H)=F∪F, tal que Fcontiene una copia monocrom´atica G0isomorfa a GoF

contiene una copia monocrom´atica H0isomorfa a H.

Deﬁnici´on 3.2. Dada la matriz A(KR(G,H)) como en la Deﬁnici´on 3.1, def´ınase la matriz M=

A(KR(G,H))2, la cual es una matriz sim´etrica y satisface las siguientes condiciones:

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 34–47

Matriz de adyacencia Ramsey 41

1) X

i>j

mij =X

i<j

mij =mij |E(KR(G,H))|=k|E(KR(G,H))|, con k=mij ∈M.

2) T raz(M) = Pn

i=1 d(vi) = 2|E(KR(G,H))|.

Deﬁnici´on 3.3. Una matriz Mcomo en la Deﬁnici´on 3.2, se dice que es lado de Ramsey si G

es bueno con respecto a H, y existen enteros t,o,p,q,r,s∈Z+, tales que se satisfacen las

siguientes relaciones geom´etricas entre los lados de los grafos G,H, y KR(G,H):

i) |E(KR(G,H))|

p=|E(G)|

qii) |E(KR(G,H))|

s=|E(H)|

riii) |E(G)|

o=|E(H)|

Deﬁnici´on 3.4. Sean GyHdos grafos simples cualesquiera, ﬁnitos y sin lazos. Sea l=

m´ax{|G|,|H|}. Una matriz Mcomo en la Deﬁnici´on 3.2 se dice que es v´ertice de Ramsey, si

existen enteros a,b,c,d,e,f∈Z+tales que se satisfacen las siguientes relaciones geom´etricas

entre los v´ertices de los grafos G,HyKl:

i) |V(KR(G,H))|

b=|V(G)|

aii) |V(KR(G,H))|

d=|V(H)|

ciii) |V(G)|

e=|V(H)|

Ejemplo 3.1. Sea G=K1,n el grafo estrella, para n≥4y sea H=K4−lel grafo diamante,

si l= m´ax{|G|,|H|} = m´ax{5,4}= 5. Luego R(G, H)=5, para n= 4.R(G, H)no puede ser 4,

pues |E(F)|<|E(G)|y|E(F)|<|E(H)|, (ver [2]).

La matriz de adyacencia de R(G, H)est´a dada por:

A(KR(G,H))=[aij ]5

i,j=1 =







0 1 1 1 1

1 0 1 1 1

1 1 0 1 1

1 1 1 0 1

1 1 1 1 0







Como M=A(KR(G,H))2, entonces







0 1 1 1 1

1 0 1 1 1

1 1 0 1 1

1 1 1 0 1

1 1 1 1 0













0 1 1 1 1

1 0 1 1 1

1 1 0 1 1

1 1 1 0 1

1 1 1 1 0













4 3 3 3 3

3 4 3 3 3

3 3 4 3 3

3 3 3 4 3

3 3 3 3 4







N´otese que M, es una matriz sim´etrica. Adem´as, como KR(G,H)es un grafo completo se tiene

que aij 6= 0 para i>j yaij 6= 0 para i<j. As´ı, mij 6= 0 para i<j ei<j. Por tanto,

i>j

mij =X

i<j

mij =3+3+3+3+3+3+3+3+3+3

= 3(1+1+1+1+1+1+1+1+1+1)=3×10 = 3 × |E(K5)|.

Luego,

i>j

mij =X

i<j

mij = 3 × |E(K5)|.

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 34–47

42 Jos´e Figueroa - Felicia Villarroel - Henry Ram´ırez - Tob´ıas Rosas

Como 3× |E(K5)|= 3 ×10 = 15 ×2, entonces existe q= 2 ∈Z+, tales que

3× |E(K5)|=2

2×(15 ×2) = 15 × |E(G)|

As´ı, 3× |E(K5)|=15 × |E(G)|

2y por tanto |E(K5)|=5× |E(G)|

i>j

mij =X

i<j

mij = 3 × |E(K5)|= 6 ×5=6× |E(H)|.

Luego, 3× |E(K5)|= 6 × |E(H)|de donde |E(K5)|= 2 × |E(H)|. La relaci´on geom´etrica entre

los lados de KR(G,H)y los lados de los grafos GyH.

Obs´ervese ahora que

|E(K5)|=5× |E(G)|

2y|E(K5)|= 2 × |E(H)|,

igualando ambos resultados se obtiene:

|E(G)|

4=|E(H)|

La relaci´on geom´etrica entre los v´ertices de KR(G,H)y entre los v´ertices de G,HyKl, a

trav´es de las matrices triangular superior e inferior esta dada a continuaci´on

i>j

mij =X

i<j

mij = 30 = 6 ×5=6|V(K5)|= 6|V(G)|

de manera que |V(K5)|=|V(G)|y as´ı existe d= 2 ∈Z+tal que

6× |V(K5)|= (15 ×2) ×2

2=15

2|V(H)|.

Luego, como |V(K5)|=|V(G)|y|V(K5)|= 5 ×|V(H)|

4e igualando las expresiones resulta:

|V(G)|

5=|V(H)|)

Ahora, la matriz Diag(M)est´a dada por

Diag(M)=[mij ×δi,j ]5

i,j=1 =







40000

04000

00400

00040

00004







As´ı,

T raz(M) = 4 + 4 + 4 + 4 + 4 = 20 = 2 ×10 = 2|E(K5)|

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 34–47

Matriz de adyacencia Ramsey 43

Ejemplo 3.2. Sea Gel grafo ´arbol del Ejemplo 2.3, Figura 3 y H=Wnel grafo rueda, para

n≥13, si l= m´ax{|G|,|H|} = m´ax{13,14}= 14, luego R(G, H) = n+ 1, para n= 13.R(G, H)

no puede ser 13, pues |E(F)|<|E(G)|y|E(F)|<|E(H)|, (ver [2]).

As´ı, KR(G,H)con R(G, H) = 14, es el menor grafo completo que, coloreado con cada secuencia

side talla m= 91, para i= 1,2,· · · ,92, satisface que Fcontiene una copia monocrom´atica G0

isomorfa a GoFcontiene una copia monocrom´atica H0isomorfa a H.

Sea la matriz de adyacencia del grafo KR(G,H), dada por

A(KR(G,H))=[aij ]14

i,j=1 =







01111111111111

10111111111111

11011111111111

11101111111111

11110111111111

11111011111111

11111101111111

11111110111111

11111111011111

11111111101111

11111111110111

11111111111011

11111111111101

11111111111110







Sea M=A(KR(G,H))2, es decir,







13 12 12 12 12 12 12 12 12 12 12 12 12 12

12 13 12 12 12 12 12 12 12 12 12 12 12 12

12 12 13 12 12 12 12 12 12 12 12 12 12 12

12 12 12 13 12 12 12 12 12 12 12 12 12 12

12 12 12 12 13 12 12 12 12 12 12 12 12 12

12 12 12 12 12 13 12 12 12 12 12 12 12 12

12 12 12 12 12 12 13 12 12 12 12 12 12 12

12 12 12 12 12 12 12 13 12 12 12 12 12 12

12 12 12 12 12 12 12 12 13 12 12 12 12 12

12 12 12 12 12 12 12 12 12 13 12 12 12 12

12 12 12 12 12 12 12 12 12 12 13 12 12 12

12 12 12 12 12 12 12 12 12 12 12 13 12 12

12 12 12 12 12 12 12 12 12 12 12 12 13 12

12 12 12 12 12 12 12 12 12 12 12 12 12 13







N´otese que M, es una matriz sim´etrica. Adem´as, como KR(G,H)es un grafo completo se tiene

aij 6= 0 para i>j yaij 6= 0 para i<j. As´ı, mij 6= 0 para i<j ei<j. Por tanto,

i>j

mij =X

i<j

mij =mij |E(KR(G,H))|= 12|E(KR(G,H))|.

i>j

mij =X

i<j

mij = 12 ×91 = 91 × |E(G)|.

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 34–47

44 Jos´e Figueroa - Felicia Villarroel - Henry Ram´ırez - Tob´ıas Rosas

i>j

mij =X

i<j

mij = 42 × |E(H)|.

La relaci´on geom´etrica entre los lados de KR(G,H), y los lados de los grafos GyH.

12 × |E(K14)|= 91 × |E(G)|=⇒|E(K14)|

91 =|E(G)|

12 = 1.

12 × |E(K14)|= 42 × |E(H)|=⇒|E(K14)|

7=|E(H)|

2= 13.

91 × |E(G)|= 42 × |E(H)|=⇒|E(G)|

6=|E(H)|

13 = 2.

La relaci´on geom´etrica entre los v´ertices de KR(G,H), y entre los v´ertices de GyHa trav´es

de las matrices triangular superior e inferior se muestra a continuaci´on

i>j

mij =X

i<j

mij = 78|V(K14)|= 84|V(G)|yX

i>j

mij = 78|V(H)|.

Luego,

78|V(K14)|= 84|V(G)|=⇒|V(K14)|

14 =|V(G)|

13 = 1

78|V(K14)|= 78|V(H)|=⇒ |V(K14)|=|V(H)|= 14,

84|V(G)|= 78|V(H)|=⇒|V(G)|

13 =|V(H)|

14 = 1.

Ahora, la matriz Diag(M)est´a dada por: Diag(M) = [mij ×δi,j ]14

i,j=1

Diag(M) =







130000000000000

013000000000000

001300000000000

000130000000000

000013000000000

000001300000000

000000130000000

000000013000000

000000001300000

000000000130000

000000000013000

000000000001300

000000000000130

000000000000013







As´ı,

T raz(M) = T raz([mij ×δi,j ]14

i,j=1) =

i=1

d(vi)=2|E(R(G, H))|.

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 34–47

Matriz de adyacencia Ramsey 45

Teorema 3.1. Sean GyHdos grafos simples cualesquiera, ﬁnitos y no vac´ıos. Si Ges bueno

con respecto a HyA(Kl) = A(KR(G,H))es la matriz de adyacencia del menor grafo completo

que contiene una copia monocrom´atica isomorfa Go una copia monocrom´atica isomorfa a H,

con M= [mij ]l

i,j=1 = (A(Kl))2, entonces se cumplen las siguientes propiedades:

1) Pi>j mij =Pi<j mij =mij |E(Kl)|=k|E(Kl)|, con k=mij ∈Z+.

2) Existen r, s ∈Z+, dependientes de E(G),E(H)yE(Kl), tales que |E(Kl)|

r=|E(G)|

3) Existen p, q ∈Z+, dependientes de V(G),V(H)yV(Kl), tales que |V(Kl)|

p=|V(H)|

4) T raz(M) =

i=1

d(vi)=2|E(Kl)|.

Demostraci´on. 1) Sean GyHdos grafos simples cualesquiera, ﬁnitos y no vac´ıos. Si Ges

bueno con respecto a H, entonces existe un conjunto de secuencias side talla m, con

i= 1,2,· · · , m + 1, donde cada si, colorea los lados del grafo completo Kl=F∪F, tal

que del grafo Fpuede extraerse al menos una copia monocrom´atica G0isomorfa G, o de F

puede extraerse al menos una copia monocrom´atica H0isomorfa H. Consid´erese la matriz de

adyacencia A(Kl) = [aij ], del menor grafo completo Kl, que contiene componentes h-buena,

la cual es sim´etrica de orden l×ly su elementos est´an dados por

aij =1 si i6=j

0 si i=j(3.1)

Def´ınase la matriz M= (A(Kl))2, tambi´en sim´etrica de orden l×l. T´omese una partici´on de

la matriz M, en tres matrices: una matriz triangular superior (mij ) con j > i, una triangular

inferior (mij ) con i>jy la matriz Diag(M). N´otese, que el n´umero de elementos distintos

de cero de Mes l2y el de la matriz Diag(M) es l(justo los elementos de la diagonal de

M). Luego, sea wel n´umero de elementos distintos de cero de la matriz triangular superior,

entonces como Mes sim´etrica se tiene que la matriz triangular inferior tiene welementos

distintos de cero, y por tanto l2=l+ 2wde donde se obtiene que w=l(l−1)

2. Como Kl

es completo y Msim´etrica, todos los elementos mij , para i6=json iguales, por la ecuaci´on

(3.1), y adem´as Pi>j mij =Pi<j mij . Sin p´erdida de generalidad,

j>i

mij = (m12 +· · · +m1l)+(m23 +· · · +m2l) + · · · + (m(l−2)l+m(l−2)l) + m(l−1)l

=m12 ×(1 + 1 + · · · + 1 + 1) = m12 ×w=m12 ×l(l−1)

2=k|E(Kl)|.

2) Usando el resultado del ´ıtem 1) se tiene que

j>i

mij =X

i>j

mij =k|E(Kl)|(3.2)

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 34–47

46 Jos´e Figueroa - Felicia Villarroel - Henry Ram´ırez - Tob´ıas Rosas

Como |E(G)|<|E(Kl)|y|E(H)|<|E(Kl)|, existen c

b,e

d,r

s∈Q+, tal que

j>i

mij =c

b|E(G)|(3.3)

j>i

mij =e

d|E(H)|(3.4)

Para la ecuaci´on (3.3) basta tomar c=k|E(Kl)|yd=|E(H)|. De forma similar para la

ecuaci´on (3.4).

Luego, igualando las ecuaciones (3.2) y (3.3) se tiene

|E(Kl)|

c=|E(G)|

kb ,

con w=kb,c6=w, ya que |E(Kl)|=|E(F)|+|E(F)|y|E(G)| ≤ |E(F)|o|E(H)|≤|E(F)|.

Igualando las ecuaciones (3.2) y (3.4) se tiene

|E(Kl)|

e=|E(H)|

kd ,

con u=kd,e6=u, puesto que |E(Kl)|=|E(F)|+|E(F)|y|E(G)|≤|E(F)|o|E(H)| ≤

|E(F)|.

Igualando las ecuaciones (3.3) y (3.4) se tiene que

|E(H)|

cd =|E(G)|

eb .

Haciendo r=be ys=cd, entonces |E(H)|

r=|E(G)|

3) Sean f, j, l, p, q, x, y, z ∈Z+, existen x

y,z

f,j

l,p

q∈Q+, tal que

j>i

mij =x

y|V(Kl)|,(3.5)

j>i

mij =z

f|V(G)|(3.6)

j>i

mij =j

l|V(H)|(3.7)

Luego, de igualando las ecuaciones (3.5) y (3.6) se tiene que

|V(Kl)|

yz =|V(G)|

xf ,

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 34–47

Matriz de adyacencia Ramsey 47

Tomando, q=xf yp=yz, entonces |V(Kl)|

p=|V(G)|

De forma similar a la anterior se igualan las ecuaciones (3.5) - (3.7), y (3.6) - (3.7), obte-

niendo respectivemente que

|V(Kl)|

yj =|V(H)|

xl y|V(G)|

fj =|V(H)|

4) Si v1, . . . , vlson los v´ertices del grafo Kl, entonces aplicando el Teorema 2.1, se obtiene que

T raz(M) =

i=1

d(vi)=2|E(Kl)|.

Referencias

[1] Diestel, R. (2000) Graph Theory. Second Edition, Spriner.

[2] Figueroa, J.; Villarroel, F.; Ram´ırez, H. y Otero, J.; Los N´umeros de Ramsey con componente

h−buena y secuencias sim´etricas, Divulgaciones Matem´aticas, 20(1) (2019), 78–90.

[3] Grassmann, Winfried K. y Tremblay, Jean-Paul. (2000) Matem´atica Discreta y L´ogica, una

perspectiva desde la ciencia de la computaci´on. 3ra reimpresi´on, Editorial Prentice Hall,

Espa˜na. IBSN 84-89660-04-2.

[4] Mann, H. B.; Two Addition Theorems, Journal of Combinatorial Theory, 8(1967). 233–235.

[5] Villaroel, F.; Figueroa, J.; M´arquez, H. and Anselmi, A.; Un m´etodo algor´ıtmico para el

calculo del n´umero Baric´entrico de Ramsey para el grafo estrella. Bol.soc. Paran. Mat. (3s)

36(2) (2018), 169–183.

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 34–47