Smooth graphs

Lajos Soukup

Displaying similar documents to “Smooth graphs”

Negative universality results for graphs

S.-D. Friedman, K. Thompson (2010)

Fundamenta Mathematicae

Similarity:

It is shown that in many forcing models there is no universal graph at the successors of regular cardinals. The proof, which is similar to the well-known proof for Cohen forcing, is extended to show that it is consistent to have no universal graph at the successor of a singular cardinal, and in particular at $ℵ_{ω + 1}$ . Previously, little was known about universality at the successors of singulars. Analogous results show it is consistent not just that there is no single graph which embeds the...

A Ramsey-style extension of a theorem of Erdős and Hajnal

Peter Komjáth (2001)

Fundamenta Mathematicae

Similarity:

If n, t are natural numbers, μ is an infinite cardinal, G is an n-chromatic graph of cardinality at most μ, then there is a graph X with $X \to (G) ¹_{μ}$ , |X| = μ⁺, such that every subgraph of X of cardinality < t is n-colorable.

Graph domination in distance two

Gábor Bacsó, Attila Tálos, Zsolt Tuza (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph, and k ≥ 1 an integer. A subgraph D is said to be k-dominating in G if every vertex of G-D is at distance at most k from some vertex of D. For a given class of graphs, Domₖ is the set of those graphs G in which every connected induced subgraph H has some k-dominating induced subgraph D ∈ which is also connected. In our notation, Dom coincides with Dom₁. In this paper we prove that $D o m D o m_{u} = D o m ₂_{u}$ holds for $_{u}$ = all connected graphs without induced $P_{u}$ (u ≥ 2). (In particular,...

On the minus domination number of graphs

Hailong Liu, Liang Sun (2004)

Czechoslovak Mathematical Journal

Similarity:

Let $G = (V, E)$ be a simple graph. A $3$ -valued function $f V (G) \to {- 1, 0, 1}$ is said to be a minus dominating function if for every vertex $v \in V$ , $f (N [v]) = \sum_{u \in N [v]} f (u) \geq 1$ , where $N [v]$ is the closed neighborhood of $v$ . The weight of a minus dominating function $f$ on $G$ is $f (V) = \sum_{v \in V} f (v)$ . The minus domination number of a graph $G$ , denoted by $γ^{-} (G)$ , equals the minimum weight of a minus dominating function on $G$ . In this paper, the following two results are obtained. (1) If $G$ is a bipartite graph of order $n$ , then $γ^{-} (G) \geq 4 (\sqrt{n + 1} - 1) - n .$ (2) For any negative integer $k$ and any positive integer...

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 signpost systems and connected graphs

Ladislav Nebeský (2005)

Czechoslovak Mathematical Journal

Similarity:

By a signpost system we mean an ordered pair $(W, P)$ , where $W$ is a finite nonempty set, $P \subseteq W \times W \times W$ and the following statements hold: $if (u, v, w) \in P, then (v, u, u) \in P and (v, u, w) \notin P, for all u, v, w \in W; if u \neq v, i then there exists r \in W such that (u, r, v) \in P, for all u, v \in W .$ We say that a signpost system $(W, P)$ is smooth if the folowing statement holds for all $u, v, x, y, z \in W$ : if $(u, v, x), (u, v, z), (x, y, z) \in P$ , then $(u, v, y) \in P$ . We say thay a signpost system $(W, P)$ is simple if the following statement holds for all $u, v, x, y \in W$ : if $(u, v, x), (x, y, v) \in P$ , then $(u, v, y), (x, y, u) \in P$ . By the underlying graph of a signpost system $(W, P)$ we mean the graph $G$ with $V (G) = W$ and such that the following statement holds for all distinct $u, v \in W$ : $u$ and $v$ are adjacent in $G$ if and...

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...

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 $\bar{P o w ₂}$ defined to be the complement of the square of a graph: $\bar{P o w ₂} (G) = \bar{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...

Domination with respect to nondegenerate properties: vertex and edge removal

Vladimir D. Samodivkin (2013)

Mathematica Bohemica

Similarity:

In this paper we present results on changing and unchanging of the domination number with respect to the nondegenerate property $𝒫$ , denoted by $γ_{𝒫} (G)$ , when a graph $G$ is modified by deleting a vertex or deleting edges. A graph $G$ is ${(γ_{𝒫} (G), k)}_{𝒫}$ -critical if $γ_{𝒫} (G - S) < γ_{𝒫} (G)$ for any set $S ⊊ V (G)$ with $| S | = k$ . Properties of ${(γ_{𝒫}, k)}_{𝒫}$ -critical graphs are studied. The plus bondage number with respect to the property $𝒫$ , denoted $b_{𝒫}^{+} (G)$ , is the cardinality of the smallest set of edges $U \subseteq E (G)$ such that $γ_{𝒫} (G - U) > γ_{𝒫} (G)$ . Some known results for ordinary domination and bondage...

Iterated neighborhood graphs

Martin Sonntag, Hanns-Martin Teichert (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The neighborhood graph N(G) of a simple undirected graph G = (V,E) is the graph $(V, E_{N})$ where $E_{N}$ = a,b | a ≠ b, x,a ∈ E and x,b ∈ E for some x ∈ V. It is well-known that the neighborhood graph N(G) is connected if and only if the graph G is connected and non-bipartite. We present some results concerning the k-iterated neighborhood graph $N^{k} (G) : = N (N (. . . N (G)))$ of G. In particular we investigate conditions for G and k such that $N^{k} (G)$ becomes a complete graph.

4-cycle properties for characterizing rectagraphs and hypercubes

Khadra Bouanane, Abdelhafid Berrachedi (2017)

Czechoslovak Mathematical Journal

Similarity:

A $(0, 2)$ -graph is a connected graph, where each pair of vertices has either 0 or 2 common neighbours. These graphs constitute a subclass of $(0, λ)$ -graphs introduced by Mulder in 1979. A rectagraph, well known in diagram geometry, is a triangle-free $(0, 2)$ -graph. $(0, 2)$ -graphs include hypercubes, folded cube graphs and some particular graphs such as icosahedral graph, Shrikhande graph, Klein graph, Gewirtz graph, etc. In this paper, we give some local properties of 4-cycles in $(0, λ)$ -graphs and more specifically...