1,721,011 research outputs found
Characterizing all trees with locating-chromatic number 3
No full textLet be a proper -coloring of a connected graph . Let be the induced partition of by , where is the partition class having all vertices with color .The color code of vertex is the ordered-tuple , where, for .If all vertices of have distinct color codes, then iscalled a locating-coloring of .The locating-chromatic number of , denoted by , isthe smallest such that posses a locating -coloring. Clearly, any graph of order have locating-chromatic number , where . Characterizing all graphswith a certain locating-chromatic number is a difficult problem. Up to now, we have known allgraphs of order with locating chromatic number or .In this paper, we characterize all trees whose locating-chromatic number . We also give a family of trees with locating-chromatic number 4
Digraphs of degree 3 and order close to the Moore bound
No full textIt is known that Moore digraphs of degree d ? 1 and diameter k ? 1 do not exist (see [20] or [5]). Furthermore, for degree 2, it is shown that for k 3 there are no digraphs of order `close' to, i.e., one less than, Moore bound [18]. In this paper, we shall consider digraphs of diameter k, degree 3 and number of vertices one less than Moore bound. We give a necessary condition for the existence of such digraphs and, using this condition, we deduce that such digraphs do not exist for infinitely many values of the diameter. Keywords --- digraphs, Moore bound, diameter, degree. 1. Introduction By a digraph we mean a structure G = (V; A) where V (G) is a nonempty set of distinct elements called vertices; and A(G) is a set of ordered pairs (u; v) of distinct vertices u; v 2 V called arcs. The order of a digraph G is the number of vertices in G, i.e., jV (G)j. An inneighbour of a vertex v in a digraph G is a vertex u such that (u; v) 2 G. Similarly, an out-neighbour of a vertex v is a v..
On the Ramsey number of 4-cycle versus wheel
No full text<div class="page" title="Page 1"><div class="layoutArea"><div class="column"><p><span>For any fixed graphs </span><span>G </span><span>and </span><span>H, </span><span>the Ramsey number </span><span>R</span><span>(</span><span>G,H</span><span>) is the smallest positive integer </span><span>n </span><span>such that for every graph </span><span>F </span><span>on </span><span>n </span><span>vertices must contain </span><span>G </span><span>or the complement of </span><span>F </span><span>contains </span><span>H. </span><span>The girth of graph </span><span>G </span><span>is a length of the shortest cycle. A </span><span>k</span><span>-regular graph with the girth </span><span>g </span><span>is called a (</span><span>k,g</span><span>)-graph. If the number of of vertices in (</span><span>k,g</span><span>)-graph is minimized then we call this graph a (</span><span>k,g</span><span>)-cage. In this paper, we derive the bounds of Ramsey number </span><span>R</span><span>(</span><span>C_</span><span>4</span><span>,W_</span><span>n</span><span>) for some values of </span><span>n</span><span>. By modifying (</span><span>k, </span><span>5)-graphs, for </span><span>k </span><span>= 7 or , we construct these corresponding (</span><span>C_</span><span>4</span><span>,W_</span><span>n</span><span>)-good graphs. </span></p></div></div></div></jats:p
On the Ramsey number of 4-cycle versus wheel
Get PDFFor any fixed graphs and , the Ramsey number is the smallest positive integer such that for every graph on vertices must contain or the complement of contains . The girth of graph is a length of the shortest cycle. A -regular graph with the girth is called a -graph. If the number of of vertices in -graph is minimized then we call this graph a -cage. In this paper, we derive the bounds of Ramsey number for some values of . By modifying -graphs, for or , we construct these corresponding -good graphs. </div
- …
