Iterated neighborhood graphs

Martin Sonntag; Hanns-Martin Teichert

Displaying similar documents to “Iterated neighborhood graphs”

Remarks on partially square graphs, hamiltonicity and circumference

Hamamache Kheddouci (2001)

Discussiones Mathematicae Graph Theory

Similarity:

Given a graph G, its partially square graph G* is a graph obtained by adding an edge (u,v) for each pair u, v of vertices of G at distance 2 whenever the vertices u and v have a common neighbor x satisfying the condition $N_{G} (x) \subseteq N_{G} [u] \cup N_{G} [v]$ , where $N_{G} [x] = N_{G} (x) \cup x$ . In the case where G is a claw-free graph, G* is equal to G². We define $σ ° ₜ = m i n \sum_{x \in S} d_{G} (x) : S i s a n i n d e p e n d e n t s e t i n G * a n d | S | = t$ . We give for hamiltonicity and circumference new sufficient conditions depending on σ° and we improve some known results.

Intersection graph of gamma sets in the total graph

T. Tamizh Chelvam, T. Asir (2012)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we consider the intersection graph $I_{Γ} (ℤ ₙ)$ of gamma sets in the total graph on ℤₙ. We characterize the values of n for which $I_{Γ} (ℤ ₙ)$ is complete, bipartite, cycle, chordal and planar. Further, we prove that $I_{Γ} (ℤ ₙ)$ is an Eulerian, Hamiltonian and as well as a pancyclic graph. Also we obtain the value of the independent number, the clique number, the chromatic number, the connectivity and some domination parameters of $I_{Γ} (ℤ ₙ)$ .

Potentially H-bigraphic sequences

Michael Ferrara, Michael Jacobson, John Schmitt, Mark Siggers (2009)

Discussiones Mathematicae Graph Theory

Similarity:

We extend the notion of a potentially H-graphic sequence as follows. Let A and B be nonnegative integer sequences. The sequence pair S = (A,B) is said to be bigraphic if there is some bipartite graph G = (X ∪ Y,E) such that A and B are the degrees of the vertices in X and Y, respectively. If S is a bigraphic pair, let σ(S) denote the sum of the terms in A. Given a bigraphic pair S, and a fixed bipartite graph H, we say that S is potentially H-bigraphic if there is some realization of...

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

A note on periodicity of the 2-distance operator

Bohdan Zelinka (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The paper solves one problem by E. Prisner concerning the 2-distance operator T₂. This is an operator on the class $C_{f}$ of all finite undirected graphs. If G is a graph from $C_{f}$ , then T₂(G) is the graph with the same vertex set as G in which two vertices are adjacent if and only if their distance in G is 2. E. Prisner asks whether the periodicity ≥ 3 is possible for T₂. In this paper an affirmative answer is given. A result concerning the periodicity 2 is added.

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

On 𝓕-independence in graphs

Frank Göring, Jochen Harant, Dieter Rautenbach, Ingo Schiermeyer (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let be a set of graphs and for a graph G let $α_{} (G)$ and $α *_{} (G)$ denote the maximum order of an induced subgraph of G which does not contain a graph in as a subgraph and which does not contain a graph in as an induced subgraph, respectively. Lower bounds on $α_{} (G)$ and $α *_{} (G)$ are presented.

The spectral determinations of the connected multicone graphs $K_{w} ▽ m P_{17}$ and $K_{w} ▽ m S$

Ali Zeydi Abdian, S. Morteza Mirafzal (2018)

Czechoslovak Mathematical Journal

Similarity:

Finding and discovering any class of graphs which are determined by their spectra is always an important and interesting problem in the spectral graph theory. The main aim of this study is to characterize two classes of multicone graphs which are determined by both their adjacency and Laplacian spectra. A multicone graph is defined to be the join of a clique and a regular graph. Let $K_{w}$ denote a complete graph on $w$ vertices, and let $m$ be a positive integer number. In A. Z. Abdian (2016)...

When a line graph associated to annihilating-ideal graph of a lattice is planar or projective

Atossa Parsapour, Khadijeh Ahmad Javaheri (2018)

Czechoslovak Mathematical Journal

Similarity:

Let $(L, \land, \lor)$ be a finite lattice with a least element 0. $𝔸 G (L)$ is an annihilating-ideal graph of $L$ in which the vertex set is the set of all nontrivial ideals of $L$ , and two distinct vertices $I$ and $J$ are adjacent if and only if $I \land J = 0$ . We completely characterize all finite lattices $L$ whose line graph associated to an annihilating-ideal graph, denoted by $𝔏 (𝔸 G (L))$ , is a planar or projective graph.

On light subgraphs in plane graphs of minimum degree five

Stanislav Jendrol&#039;, Tomáš Madaras (1996)

Discussiones Mathematicae Graph Theory

Similarity:

A subgraph of a plane graph is light if the sum of the degrees of the vertices of the subgraph in the graph is small. It is well known that a plane graph of minimum degree five contains light edges and light triangles. In this paper we show that every plane graph of minimum degree five contains also light stars $K_{1, 3}$ and $K_{1, 4}$ and a light 4-path P₄. The results obtained for $K_{1, 3}$ and P₄ are best possible.

On the order of certain close to regular graphs without a matching of given size

Sabine Klinkenberg, Lutz Volkmann (2007)

Czechoslovak Mathematical Journal

Similarity:

A graph $G$ is a ${d, d + k}$ -graph, if one vertex has degree $d + k$ and the remaining vertices of $G$ have degree $d$ . In the special case of $k = 0$ , the graph $G$ is $d$ -regular. Let $k, p \geq 0$ and $d, n \geq 1$ be integers such that $n$ and $p$ are of the same parity. If $G$ is a connected ${d, d + k}$ -graph of order $n$ without a matching $M$ of size $2 | M | = n - p$ , then we show in this paper the following: If $d = 2$ , then $k \geq 2 (p + 2)$ and (i) $n \geq k + p + 6$ . If $d \geq 3$ is odd and $t$ an integer with $1 \leq t \leq p + 2$ , then (ii) $n \geq d + k + 1$ for $k \geq d (p + 2)$ , (iii) $n \geq d (p + 3) + 2 t + 1$ for $d (p + 2 - t) + t \leq k \leq d (p + 3 - t) + t - 3$ , (iv) $n \geq d (p + 3) + 2 p + 7$ for $k \leq p$ . If $d \geq 4$ is even, then (v) $n \geq d + k + 2 - η$ for $k \geq d (p + 3) + p + 4 + η$ , (vi) $n \geq d + k + p + 2 - 2 t = d (p + 4) + p + 6$ for $k = d (p + 3) + 4 + 2 t$ and $p \geq 1$ ,...