The path space of a higher-rank graph

Samuel B. G. Webster

The search session has expired. Please query the service again.

Displaying similar documents to “The path space of a higher-rank graph”

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.

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

Nonempty intersection of longest paths in a graph with a small matching number

Fuyuan Chen (2015)

Czechoslovak Mathematical Journal

Similarity:

A maximum matching of a graph $G$ is a matching of $G$ with the largest number of edges. The matching number of a graph $G$ , denoted by $α^{'} (G)$ , is the number of edges in a maximum matching of $G$ . In 1966, Gallai conjectured that all the longest paths of a connected graph have a common vertex. Although this conjecture has been disproved, finding some nice classes of graphs that support this conjecture is still very meaningful and interesting. In this short note, we prove that Gallai’s conjecture...

The induced paths in a connected graph and a ternary relation determined by them

Ladislav Nebeský (2002)

Mathematica Bohemica

Similarity:

By a ternary structure we mean an ordered pair $(X_{0}, T_{0})$ , where $X_{0}$ is a finite nonempty set and $T_{0}$ is a ternary relation on $X_{0}$ . By the underlying graph of a ternary structure $(X_{0}, T_{0})$ we mean the (undirected) graph $G$ with the properties that $X_{0}$ is its vertex set and distinct vertices $u$ and $v$ of $G$ are adjacent if and only if ${x \in X_{0} T_{0} (u, x, v)} \cup {x \in X_{0} T_{0} (v, x, u)} = {u, v} .$ A ternary structure $(X_{0}, T_{0})$ is said to be the B-structure of a connected graph $G$ if $X_{0}$ is the vertex set of $G$ and the following statement holds for all $u, x, y \in X_{0}$ : $T_{0} (x, u, y)$ if and only if $u$ belongs to an...

The Wiener number of powers of the Mycielskian

Rangaswami Balakrishnan, S. Francis Raj (2010)

Discussiones Mathematicae Graph Theory

Similarity:

The Wiener number of a graph G is defined as $1 / 2 \sum_{u, v \in V (G)} d (u, v)$ , d the distance function on G. The Wiener number has important applications in chemistry. We determine a formula for the Wiener number of an important graph family, namely, the Mycielskians μ(G) of graphs G. Using this, we show that for k ≥ 1, $W (μ (S ₙ^{k})) \leq W (μ (T ₙ^{k})) \leq W (μ (P ₙ^{k}))$ , where Sₙ, Tₙ and Pₙ denote a star, a general tree and a path on n vertices respectively. We also obtain Nordhaus-Gaddum type inequality for the Wiener number of $μ (G^{k})$ .

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.

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.

Special m-hyperidentities in biregular leftmost graph varieties of type (2,0)

Apinant Anantpinitwatna, Tiang Poomsa-ard (2009)

Discussiones Mathematicae - General Algebra and Applications

Similarity:

Graph algebras establish a connection between directed graphs without multiple edges and special universal algebras of type (2,0). We say that a graph G satisfies a term equation s ≈ t if the corresponding graph algebra $\underset{̲}{A (G)}$ satisfies s ≈ t. A class of graph algebras V is called a graph variety if $V = M o d_{g} Σ$ where Σ is a subset of T(X) × T(X). A graph variety $V^{'} = M o d_{g} Σ^{'}$ is called a biregular leftmost graph variety if Σ’ is a set of biregular leftmost term equations. A term equation s ≈ t is called an identity...

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

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

Stronger bounds for generalized degrees and Menger path systems

R.J. Faudree, Zs. Tuza (1995)

Discussiones Mathematicae Graph Theory

Similarity:

For positive integers d and m, let $P_{d, m} (G)$ denote the property that between each pair of vertices of the graph G, there are m internally vertex disjoint paths of length at most d. For a positive integer t a graph G satisfies the minimum generalized degree condition δₜ(G) ≥ s if the cardinality of the union of the neighborhoods of each set of t vertices of G is at least s. Generalized degree conditions that ensure that $P_{d, m} (G)$ is satisfied have been investigated. In particular, it has been shown,...

Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs

Éric Sopena (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The oriented chromatic number of an oriented graph $^{\to} G$ is the minimum order of an oriented graph $^{\to} H$ such that $^{\to} G$ admits a homomorphism to $^{\to} H$ . The oriented chromatic number of an undirected graph G is then the greatest oriented chromatic number of its orientations. In this paper, we introduce the new notion of the upper oriented chromatic number of an undirected graph G, defined as the minimum order of an oriented graph $^{\to} U$ such that every orientation $^{\to} G$ of G admits a homomorphism to $^{\to} U$ . We give...