Displaying similar documents to “On Ramsey ( K 1 , 2 , K ) -minimal graphs”

On Ramsey ( K 1 , 2 , C ) -minimal graphs

Tomás Vetrík, Lyra Yulianti, Edy Tri Baskoro (2010)

Discussiones Mathematicae Graph Theory

Similarity:

For graphs F, G and H, we write F → (G,H) to mean that any red-blue coloring of the edges of F contains a red copy of G or a blue copy of H. The graph F is Ramsey (G,H)-minimal if F → (G,H) but F* ↛ (G,H) for any proper subgraph F* ⊂ F. We present an infinite family of Ramsey ( K 1 , 2 , C ) -minimal graphs of any diameter ≥ 4.

Minimal rankings of the Cartesian product Kₙ ☐ Kₘ

Gilbert Eyabi, Jobby Jacob, Renu C. Laskar, Darren A. Narayan, Dan Pillone (2012)

Discussiones Mathematicae Graph Theory

Similarity:

For a graph G = (V, E), a function f:V(G) → 1,2, ...,k is a k-ranking if f(u) = f(v) implies that every u - v path contains a vertex w such that f(w) > f(u). A k-ranking is minimal if decreasing any label violates the definition of ranking. The arank number, ψ r ( G ) , of G is the maximum value of k such that G has a minimal k-ranking. We completely determine the arank number of the Cartesian product Kₙ ☐ Kₙ, and we investigate the arank number of Kₙ ☐ Kₘ where n > m.

Rotation and jump distances between graphs

Gary Chartrand, Heather Gavlas, Héctor Hevia, Mark A. Johnson (1997)

Discussiones Mathematicae Graph Theory

Similarity:

A graph H is obtained from a graph G by an edge rotation if G contains three distinct vertices u,v, and w such that uv ∈ E(G), uw ∉ E(G), and H = G-uv+uw. A graph H is obtained from a graph G by an edge jump if G contains four distinct vertices u,v,w, and x such that uv ∈ E(G), wx∉ E(G), and H = G-uv+wx. If a graph H is obtained from a graph G by a sequence of edge jumps, then G is said to be j-transformed into H. It is shown that for every two graphs G and H of the same order (at least...

On 2-periodic graphs of a certain graph operator

Ivan Havel, Bohdan Zelinka (2001)

Discussiones Mathematicae Graph Theory

Similarity:

We deal with the graph operator P o w ¯ defined to be the complement of the square of a graph: P o w ¯ ( G ) = P o w ( G ) ¯ . Motivated by one of many open problems formulated in [6] we look for graphs that are 2-periodic with respect to this operator. We describe a class of bipartite graphs possessing the above mentioned property and prove that for any m,n ≥ 6, the complete bipartite graph K m , n can be decomposed in two edge-disjoint factors from . We further show that all the incidence graphs of Desarguesian finite projective...

Set colorings in perfect graphs

Ralucca Gera, Futaba Okamoto, Craig Rasmussen, Ping Zhang (2011)

Mathematica Bohemica

Similarity:

For a nontrivial connected graph G , let c : V ( G ) be a vertex coloring of G where adjacent vertices may be colored the same. For a vertex v V ( G ) , the neighborhood color set NC ( v ) is the set of colors of the neighbors of v . The coloring c is called a set coloring if NC ( u ) NC ( v ) for every pair u , v of adjacent vertices of G . The minimum number of colors required of such a coloring is called the set chromatic number χ s ( G ) . We show that the decision variant of determining χ s ( G ) is NP-complete in the general case, and show that...

Uniquely partitionable graphs

Jozef Bucko, Marietjie Frick, Peter Mihók, Roman Vasky (1997)

Discussiones Mathematicae Graph Theory

Similarity:

Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition of the vertex set V(G) into subsets V₁, ...,Vₙ such that the subgraph G [ V i ] induced by V i has property i ; i = 1,...,n. A graph G is said to be uniquely (₁, ...,ₙ)-partitionable if G has exactly one (₁,...,ₙ)-partition. A property is called hereditary if every subgraph of every graph with property also has property . If every graph that is a disjoint union of two graphs that have property also has property...

Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties

Ewa Drgas-Burchardt (2009)

Discussiones Mathematicae Graph Theory

Similarity:

An additive hereditary graph property is any class of simple graphs, which is closed under isomorphisms unions and taking subgraphs. Let L a denote a class of all such properties. In the paper, we consider H-reducible over L a properties with H being a fixed graph. The finiteness of the sets of all minimal forbidden graphs is analyzed for such properties.

Destroying symmetry by orienting edges: complete graphs and complete bigraphs

Frank Harary, Michael S. Jacobson (2001)

Discussiones Mathematicae Graph Theory

Similarity:

Our purpose is to introduce the concept of determining the smallest number of edges of a graph which can be oriented so that the resulting mixed graph has the trivial automorphism group. We find that this number for complete graphs is related to the number of identity oriented trees. For complete bipartite graphs K s , t , s ≤ t, this number does not always exist. We determine for s ≤ 4 the values of t for which this number does exist.

Clopen graphs

Stefan Geschke (2013)

Fundamenta Mathematicae

Similarity:

A graph G on a topological space X as its set of vertices is clopen if the edge relation of G is a clopen subset of X² without the diagonal. We study clopen graphs on Polish spaces in terms of their finite induced subgraphs and obtain information about their cochromatic numbers. In this context we investigate modular profinite graphs, a class of graphs obtained from finite graphs by taking inverse limits. This continues the investigation of continuous colorings on Polish spaces and their...

On integral sum graphs with a saturated vertex

Zhibo Chen (2010)

Czechoslovak Mathematical Journal

Similarity:

As introduced by F. Harary in 1994, a graph G is said to be an i n t e g r a l s u m g r a p h if its vertices can be given a labeling f with distinct integers so that for any two distinct vertices u and v of G , u v is an edge of G if and only if f ( u ) + f ( v ) = f ( w ) for some vertex w in G . We prove that every integral sum graph with a saturated vertex, except the complete graph K 3 , has edge-chromatic number equal to its maximum degree. (A vertex of a graph G is said to be if it is adjacent to every...

Structure of the set of all minimal total dominating functions of some classes of graphs

K. Reji Kumar, Gary MacGillivray (2010)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we study some of the structural properties of the set of all minimal total dominating functions ( T ) of cycles and paths and introduce the idea of function reducible graphs and function separable graphs. It is proved that a function reducible graph is a function separable graph. We shall also see how the idea of function reducibility is used to study the structure of T ( G ) for some classes of graphs.

New edge neighborhood graphs

Ali A. Ali, Salar Y. Alsardary (1997)

Czechoslovak Mathematical Journal

Similarity:

Let G be an undirected simple connected graph, and e = u v be an edge of G . Let N G ( e ) be the subgraph of G induced by the set of all vertices of G which are not incident to e but are adjacent to u or v . Let 𝒩 e be the class of all graphs H such that, for some graph G , N G ( e ) H for every edge e of G . Zelinka [3] studied edge neighborhood graphs and obtained some special graphs in 𝒩 e . Balasubramanian and Alsardary [1] obtained some other graphs in 𝒩 e . In this paper we given some new graphs in 𝒩 e .

A Finite Characterization and Recognition of Intersection Graphs of Hypergraphs with Rank at Most 3 and Multiplicity at Most 2 in the Class of Threshold Graphs

Yury Metelsky, Kseniya Schemeleva, Frank Werner (2017)

Discussiones Mathematicae Graph Theory

Similarity:

We characterize the class [...] L32 L 3 2 of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs. We also give an O(n)-time algorithm for the recognition of graphs from [...] L32 L 3 2 in the class of threshold graphs, where n is the number of vertices of a tested graph.

Symmetries of embedded complete bipartite graphs

Erica Flapan, Nicole Lehle, Blake Mellor, Matt Pittluck, Xan Vongsathorn (2014)

Fundamenta Mathematicae

Similarity:

We characterize which automorphisms of an arbitrary complete bipartite graph K n , m can be induced by a homeomorphism of some embedding of the graph in S³.

Difference labelling of cacti

Martin Sonntag (2003)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G is a difference graph iff there exists S ⊂ IN⁺ such that G is isomorphic to the graph DG(S) = (V,E), where V = S and E = i,j:i,j ∈ V ∧ |i-j| ∈ V. It is known that trees, cycles, complete graphs, the complete bipartite graphs K n , n and K n , n - 1 , pyramids and n-sided prisms (n ≥ 4) are difference graphs (cf. [4]). Giving a special labelling algorithm, we prove that cacti with a girth of at least 6 are difference graphs, too.

On well-covered graphs of odd girth 7 or greater

Bert Randerath, Preben Dahl Vestergaard (2002)

Discussiones Mathematicae Graph Theory

Similarity:

A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer [14] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. One of the most challenging problems in this area, posed in the survey of Plummer [15], is to find a good characterization of well-covered graphs of girth 4. We examine several subclasses of well-covered graphs of girth ≥ 4 with respect to the odd girth...