Irregularity strength of regular graphs.
Isolated trees in a bichromatic random graph
Isolated trees in a random graph
Isometric classification of Sobolev spaces on graphs
Isometric Sobolev spaces on finite graphs are characterized. The characterization implies that the following analogue of the Banach-Stone theorem is valid: if two Sobolev spaces on 3-connected graphs, with the exponent which is not an even integer, are isometric, then the corresponding graphs are isomorphic. As a corollary it is shown that for each finite group and each p which is not an even integer, there exists n ∈ ℕ and a subspace whose group of isometries is the direct product × ℤ₂.
Isomorphic components of direct products of bipartite graphs
A standard result states the direct product of two connected bipartite graphs has exactly two components. Jha, Klavžar and Zmazek proved that if one of the factors admits an automorphism that interchanges partite sets, then the components are isomorphic. They conjectured the converse to be true. We prove the converse holds if the factors are square-free. Further, we present a matrix-theoretic conjecture that, if proved, would prove the general case of the converse; if refuted, it would produce a...
Isomorphic components of Kronecker product of bipartite graphs
Weichsel (Proc. Amer. Math. Soc. 13 (1962) 47-52) proved that the Kronecker product of two connected bipartite graphs consists of two connected components. A condition on the factor graphs is presented which ensures that such components are isomorphic. It is demonstrated that several familiar and easily constructible graphs are amenable to that condition. A partial converse is proved for the above condition and it is conjectured that the converse is true in general.
Isomorphic digraphs from powers modulo
Let be a prime. We assign to each positive number a digraph whose set of vertices is and there exists a directed edge from a vertex to a vertex if . In this paper we obtain a necessary and sufficient condition for .
Isomorphic factorisations of complete graphs into factors with a given diameter
Isomorphism-induced line isomorphisms on pseudographs
Isomorphisms and traversability of directed path graphs
The concept of a line digraph is generalized to that of a directed path graph. The directed path graph Pₖ(D) of a digraph D is obtained by representing the directed paths on k vertices of D by vertices. Two vertices are joined by an arc whenever the corresponding directed paths in D form a directed path on k+1 vertices or form a directed cycle on k vertices in D. In this introductory paper several properties of P₃(D) are studied, in particular with respect to isomorphism and traversability. In our...
Isomorphisms of Cayley graphs of a free Abelian group.
Isomorphisms of cyclic abelian covers of symmetric digraphs. II.
Isomorphisms of polar and polarized graphs
Isomorphisms of products of infinite connected graphs
Isomorphisms of products of infinite graphs
Isoperimetric numbers and spectral radius of some infinite planar graphs
Isospectral graphs and isospectral surfaces
Isotopy of digraphs
Iterated arc graphs
The arc graph of a digraph is the digraph with the set of arcs of as vertex-set, where the arcs of join consecutive arcs of . In 1981, S. Poljak and V. Rödl characterized the chromatic number of in terms of the chromatic number of when is symmetric (i.e., undirected). In contrast, directed graphs with equal chromatic numbers can have arc graphs with distinct chromatic numbers. Even though the arc graph of a symmetric graph is not symmetric, we show that the chromatic number of the...
Iterated neighborhood graphs
The neighborhood graph N(G) of a simple undirected graph G = (V,E) is the graph where = 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 of G. In particular we investigate conditions for G and k such that becomes a complete graph.