Graph related

[kohmoto]

     Hello, seqfans.

     This is a sequence from OEUAI.
    　ID Number :　　B020004
　　Sequence :　　 7, 12,
　　　　　　　　　
　　Name :　　　　　Chromatic number of Near_{2,3}(G_k).
   　　　　　　　　　 Where G_k is graphs on a surface with k holes.

　 　　  　　　　　　　A mapping Near_{n,m} : H -> H' is defined as follows.
　　  　　  　　　　　 If we add all edges between two vertices which are　(m,n)　on H, then H becomes Near_{m,n}(H).
　　　　　　  　　　　Definition of (m,n) :
　　　　　　　   　　 n edges of length m exist between different two 
vertices.
                        Example :
                        If V={x,y,a,b,c} , E={xa, xb, xc, ay, by, cy} , then 
x,y is (2,3).
                        If a graph is like this o-o-o , then the virtices of 
both sides is (2,1).

 　Comment :      a(0)=1 is proved. a(1)=12 is lower bound.
                   　    I am not sure at all that the Heawood like formula 
is correct.

                        Kai(Near_{2,3}(G(E)) = [(13 + (169 - 48*E)^(1/2))/2]
                                     E     0,   1,   2,   3,   4,   5
                                           13, 14, 15, 17, 18, 19
                              where  G(E) is a graph which has Euler number 
E, E<=0

                         I dont'n remember the reason why I made it.

　 Keyword :　　　 unknown
　 Offset :　1
　 Author : Yasutoshi



    To know the Chromatic number of Near_{2,3}(G_k) is rather dificult.
    So, I considered a little more easy        .

    %S A000001 7, 12,
    %N A000001 a(k)=Minimal number of vertices of a S_k graph which 
satisfies the following condition.

                     C:   For all two different vertices on a graph,
                           an edge exists between them
                           or,
                           three paths of length two exist between them.

                     Where S_k means a surface with k holes.

    %C A000001 The formula might give a upper bound.

    For example, if we search the existance of a graph with 14 nodes which 
satisfies the condition using a computer, the number of all graphs is 
2^C_{14,2} = 2^91= 30 digits
    The digits is too large to do  exhaustive search, but if some good 
algorithm exists, it might possible to find the graph.

    Yasutoshi

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20050315/d2b91b72/attachment.htm>