On Ramsey (3K2,P3)-minimal graphs

Muhshi, Hadi; Baskoro, Edy Tri
May 2012
AIP Conference Proceedings;5/22/2012, Vol. 1450 Issue 1, p110
Academic Journal
For any given two graphs G and H, we use the notation F→(G,H) to mean that in any red-blue coloring of the edges of F, the following must hold: F contains either a red subgraph G or a blue subgraph H. A graph F is a Ramsey (G,H)-minimal graph if F→(G,H) but F*↛(G,H) for any proper subgraph F* of F. Let R(G,H) be the class of all Ramsey (G,H)-minimal graphs. In this paper, we derive the properties of graphs belonging to R(3K2,P3). By using these properties we determine all graphs belonging to this class.


Related Articles

  • On Ramsey (2K2, 2Pn)-minimal graphs. Tatanto, Dedy; Baskoro, Edy Tri // AIP Conference Proceedings;5/22/2012, Vol. 1450 Issue 1, p90 

    Let G and H be two given graphs. The notation F → (G,H) means that any red-blue coloring on the edges of F will create either a red subgraph G or a blue subgraph H in F. A graph F is a Ramsey (G,H)-minimal graph if F satisfies two conditions: (1) F → (G,H), and (2) F* ↛...

  • A characterization of the corona product of a cycle with some graphs based on its f-chromatic index. Adiwijaya; Salman, A. N. M.; Suprijanto, Djoko; Baskoro, Edy Tri // AIP Conference Proceedings;5/22/2012, Vol. 1450 Issue 1, p155 

    An f-coloring of graph G(V,E) is a generalized edge-coloring such that every vertex ν in V has at most f(ν) edges colored with a same color. There are many applications of the f-coloring, for instance we can use it in order to solve some scheduling problems and some network design...

  • Further results on partition dimension of corona products. Darmaji; Baskoro, Edy Tri // AIP Conference Proceedings;5/22/2012, Vol. 1450 Issue 1, p77 

    The problem of finding of the partition dimension for a general graph is an NP-hard problem. Therefore, many studies of partition dimension of graphs are focused on particular classes of graphs. In this paper, we are interested in determining the partition dimension for the resulting graphs...

  • Exponents of two-colored digraphs consisting of two cycles. Suwilo, Saib // AIP Conference Proceedings;5/22/2012, Vol. 1450 Issue 1, p297 

    A two-colored digraph D(2) is a digraph D whose each of its arc is colored by either red or blue. For nonnegative integers s and t with s+t > 0, an (s, t)-walk in a two-colored digraph is a walk of length s+t consisting of s red arcs and t blue arcs. The vector (s, t)T is the composition of the...

  • RAINBOW CONNECTION NUMBER OF DENSE GRAPHS. XUELIANG LI; MENGMENG LIU; SCHIERMEYER, INGO // Discussiones Mathematicae: Graph Theory;2013, Vol. 33 Issue 3, p603 

    An edge-colored graph G is rainbow connected, if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In this paper we...

  • Some Conclusion on Unique k-List Colorable Complete Multipartite Graphs. Yanning Wang; Yanyan Wang; Xuguang Zhang // Journal of Applied Mathematics;2013, p1 

    If a graph G admits a k-list assignment L such that G has a unique L-coloring, then G is called uniquely k-list colorable graph, or UkLC graph for short. In the process of characterizing UkLC graphs, the complete multipartite graphs K1*r,s, (r, s ε N) are often researched. But it is usually...

  • The ErdÅ‘s–Gyárfás problem on generalized Ramsey numbers. Conlon, David; Fox, Jacob; Lee, Choongbum; Sudakov, Benny // Proceedings of the London Mathematical Society;Jan2015, Vol. 110 Issue 1, p1 

    Fix positive integers $p$ and $q$ with $2 \leq q \leq {p \choose 2}$. An edge coloring of the complete graph $K_n$ is said to be a $(p, q)$-coloring if every $K_p$ receives at least $q$ different colors. The function $f(n, p, q)$ is the minimum number of colors that are needed for $K_n$ to have...

  • Distributed Graph Algorithms and their Complexity: An Introduction. IZUMI, Taisuke // Interdisciplinary Information Sciences;2015, Vol. 21 Issue 4, p351 

    Distributed graph algorithms are the methods for solving graph problems defined over networks of computers, where each vertex is a computing entity (i.e., process) and an edge is a communication link between two processes. This introductory survey presents a brief outline, several important...

  • COGNITIVE MAPPING.  // Encyclopedia of Operations Research & Management Science;2001, p94 

    A definition of the term "cognitive mapping" is presented. It refers to a graphical notation for capturing concepts in use by decision makers for understanding a problematic situation. It is cross-referenced with problem structuring methods.


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics