Asymptotic spectral distributions of distance-k graphs of Cartesian product graphs

Yuji Hibino; Hun Hee Lee; Nobuaki Obata

Displaying similar documents to “Asymptotic spectral distributions of distance-k graphs of Cartesian product graphs”

On the Spectral Characterizations of Graphs

Jing Huang, Shuchao Li (2017)

Discussiones Mathematicae Graph Theory

Similarity:

Several matrices can be associated to a graph, such as the adjacency matrix or the Laplacian matrix. The spectrum of these matrices gives some informations about the structure of the graph and the question “Which graphs are determined by their spectrum?” is still a difficult problem in spectral graph theory. Let [...] p2q $𝒰_{p}^{2 q}$ be the set of graphs obtained from Cp by attaching two pendant edges to each of q (q ⩽ p) vertices on Cp, whereas [...] p2q $𝒱_{p}^{2 q}$ the subset of [...] p2q $𝒰_{p}^{2 q}$ with odd p...

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

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

Unicyclic graphs with bicyclic inverses

Swarup Kumar Panda (2017)

Czechoslovak Mathematical Journal

Similarity:

A graph is nonsingular if its adjacency matrix $A (G)$ is nonsingular. The inverse of a nonsingular graph $G$ is a graph whose adjacency matrix is similar to $A {(G)}^{- 1}$ via a particular type of similarity. Let $ℋ$ denote the class of connected bipartite graphs with unique perfect matchings. Tifenbach and Kirkland (2009) characterized the unicyclic graphs in $ℋ$ which possess unicyclic inverses. We present a characterization of unicyclic graphs in $ℋ$ which possess bicyclic inverses.

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

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.

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.

Unbalanced unicyclic and bicyclic graphs with extremal spectral radius

Francesco Belardo, Maurizio Brunetti, Adriana Ciampella (2021)

Czechoslovak Mathematical Journal

Similarity:

A signed graph $Γ$ is a graph whose edges are labeled by signs. If $Γ$ has $n$ vertices, its spectral radius is the number $ρ (Γ) : = max {| λ_{i} (Γ) | : 1 \leq i \leq n}$ , where $λ_{1} (Γ) \geq \dots \geq λ_{n} (Γ)$ are the eigenvalues of the signed adjacency matrix $A (Γ)$ . Here we determine the signed graphs achieving the minimal or the maximal spectral radius in the classes $𝔘_{n}$ and $𝔅_{n}$ of unbalanced unicyclic graphs and unbalanced bicyclic graphs, respectively.

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.

Restrained domination in unicyclic graphs

Johannes H. Hattingh, Ernst J. Joubert, Marc Loizeaux, Andrew R. Plummer, Lucas van der Merwe (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted by $γ_{r} (G)$ , is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then $γ_{r} (U) \geq ⎡ n / 3 ⎤$ , and provide a characterization of graphs achieving this bound.

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

Histories in path graphs

Ludovít Niepel (2007)

Discussiones Mathematicae Graph Theory

Similarity:

For a given graph G and a positive integer r the r-path graph, $P_{r} (G)$ , has for vertices the set of all paths of length r in G. Two vertices are adjacent when the intersection of the corresponding paths forms a path of length r-1, and their union forms either a cycle or a path of length k+1 in G. Let $P_{r}^{k} (G)$ be the k-iteration of r-path graph operator on a connected graph G. Let H be a subgraph of $P_{r}^{k} (G)$ . The k-history $P_{r}^{- k} (H)$ is a subgraph of G that is induced by all edges that take part in the recursive...