TITLE

ON RAMSEY (K1,2,Kn)-MINIMAL GRAPHS

AUTHOR(S)
HAŁUSZCZAK, MARIUSZ
PUB. DATE
May 2012
SOURCE
Discussiones Mathematicae: Graph Theory;2012, Vol. 32 Issue 2, p331
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
Let F be a graph and let G, H denote nonempty families of graphs. We write F → (G,H) if in any 2-coloring of edges of F with red and blue, there is a red subgraph isomorphic to some graph from G or a blue subgraph isomorphic to some graph from H. The graph F without isolated vertices is said to be a (G,H)-minimal graph if F → (G,H) and F - e ↛ (G,H) for every e ε E(F). We present a technique which allows to generate infinite family of (G,H)- minimal graphs if we know some special graphs. In particular, we show how to receive infinite family of (K1,2,Kn)-minimal graphs, for every n = 3.
ACCESSION #
86440297

 

Related Articles

  • On Three-Color Ramsey Number of Paths. Maherani, L.; Omidi, G.; Raeisi, G.; Shahsiah, M. // Graphs & Combinatorics;Nov2015, Vol. 31 Issue 6, p2299 

    For given graphs $$G_1, G_2, \ldots , G_t$$ , the multicolor Ramsey number $$R(G_1, G_2, \ldots , G_t)$$ is the smallest positive integer $$n$$ , such that if the edges of the complete graph $$K_n$$ are partitioned into $$t$$ disjoint color classes giving $$t$$ graphs $$H_1,H_2,\ldots ,H_t$$ ,...

  • ON RAMSEY (K1,2, Kn)-MINIMAL GRAPHS. Haluszczak, Mariusz // Discussiones Mathematicae: Graph Theory;2012, Vol. 32 Issue 3, p331 

    Let F be a graph and let G, H denote nonempty families of graphs. We write F → (G, H) if in any 2-coloring of edges of F with red and blue, there is a red subgraph isomorphic to some graph from G or a blue subgraph isomorphic to some graph from H. The graph F without isolated vertices is...

  • Ideal Graph of a Graph. Manoharan, R.; Vasuki, R.; Manisekaran, R. // International Journal of Mathematical Combinatorics;Sep2011, Vol. 3, p11 

    In this paper, we introduce ideal graph of a graph and study some of its properties. We characterize connectedness, isomorphism of graphs and coloring property of a graph using ideal graph. Also, we give an upper bound for chromatic number of a graph.

  • ON THE RAINBOW CONNECTION OF CARTESIAN PRODUCTS AND THEIR SUBGRAPHS. KLAVžAR, SANDI; MEKIš, GAšPER // Discussiones Mathematicae: Graph Theory;2012, Vol. 32 Issue 4, p783 

    Rainbow connection number of Cartesian products and their subgraphs are considered. Previously known bounds are compared and non-existence of such bounds for subgraphs of products are discussed. It is shown that the rainbow connection number of an isometric subgraph of a hypercube is bounded...

  • FROM RECONSTRUCTION CONJECTURE TOWARDS A LEMMA. Banerjee, Subhashis; Sensarma, Debajit; Basuli, Krishnendu; Naskar, Saptarshi; Sarma, Samar Sen // Computer Science & Engineering;Feb2012, Vol. 2 Issue 1, p53 

    The Reconstruction Conjecture has been synthesized under the characterized of matching Polynomial. A Polynomial time algorithm for generating matching polynomial of an undirected graph is given. Algorithms are given for reconstructing a graph from its node-deleted and edge-deleted subgraphs....

  • Characterization and Construction of Permutation Graphs. Gervacio, Severino V.; Rapanut, Teofina A.; Ramos, Phoebe Chloe F. // Open Journal of Discrete Mathematics;Jan2013, Vol. 3 Issue 1, p33 

    If σ is a permutation of {1, 2,---,n} , the graph Gσ has vertices 1, 2,---,n where xy is an edge of Gσ if and only if ( x, y) or ( y, x) is an inversion of σ . Any graph isomorphic to Gσ is called a permutation graph. In 1967 Gallai characterized permutation graphs in terms of...

  • Highly Hamiltonian K1,3P4-Free Graphs. Ramos, R. E.; Babierra, A. L. // Southeast Asian Bulletin of Mathematics;2012, Vol. 36 Issue 4, p529 

    A graph G is K1,3P4-free if G contains no induced subgraph isomorphic to K1,3 nor P4. We characterize here the fully cycle extendable 2-connected K1,3P4-free graphs, the panconnected 3-connected K1,3P4-free graphs, the path extendable 3-connected K1,3P4-free graphs, and the q-edge hamiltonian...

  • Universal H-Colourable Graphs. Broere, Izak; Heidema, Johannes // Graphs & Combinatorics;Sep2013, Vol. 29 Issue 5, p1193 

    Rado constructed a (simple) denumerable graph R with the positive integers as vertex set with the following edges: for given m and n with m < n, m is adjacent to n if n has a 1 in the mth position of its binary expansion. It is well known that R is a universal graph in the set...

  • Small Edge Sets Meeting all Triangles of a Graph. Aparna Lakshmanan, S.; Bujtás, Cs.; Tuza, Zs. // Graphs & Combinatorics;May2012, Vol. 28 Issue 3, p381 

    It was conjectured in 1981 by the third author that if a graph G does not contain more than t pairwise edge-disjoint triangles, then there exists a set of at most 2 t edges that shares an edge with each triangle of G. In this paper, we prove this conjecture for odd-wheel-free graphs and for...

Share

Read the Article

Courtesy of VIRGINIA BEACH PUBLIC LIBRARY AND SYSTEM

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

Try another library?
Sign out of this library

Other Topics