Eigenvalue Conditions for Induced Subgraphs
Necessary conditions for an undirected graph G to contain a graph H as induced subgraph involving the smallest ordinary or the largest normalized Laplacian eigenvalue of G are presented.
Eigenvectors and reconstruction.
Embedding a forest in a graph.
Embeddings of hamiltonian paths in faulty k-ary 2-cubes
It is well known that the k-ary n-cube has been one of the most efficient interconnection networks for distributed-memory parallel systems. A k-ary n-cube is bipartite if and only if k is even. Let (X,Y) be a bipartition of a k-ary 2-cube (even integer k ≥ 4). In this paper, we prove that for any two healthy vertices u ∈ X, v ∈ Y, there exists a hamiltonian path from u to v in the faulty k-ary 2-cube with one faulty vertex in each part.
Equivalences between isomorphism classes on infinite graphs
The paper studies some equivalence relations between isomorphism classes of countable graphs which correspond in a certain sense to various distances between isomorphism classes of finite graphs.
Finite graphs and digraphs which are not reconstructible from their cardinality restricted subgraphs
Frucht’s Theorem for the Digraph Factorial
To every graph (or digraph) A, there is an associated automorphism group Aut(A). Frucht’s theorem asserts the converse association; that for any finite group G there is a graph (or digraph) A for which Aut(A) ∼= G. A new operation on digraphs was introduced recently as an aid in solving certain questions regarding cancellation over the direct product of digraphs. Given a digraph A, its factorial A! is certain digraph whose vertex set is the permutations of V (A). The arc set E(A!) forms a group,...
Graph fibrations, graph isomorphism, and PageRank
PageRank is a ranking method that assigns scores to web pages using the limit distribution of a random walk on the web graph. A fibration of graphs is a morphism that is a local isomorphism of in-neighbourhoods, much in the same way a covering projection is a local isomorphism of neighbourhoods. We show that a deep connection relates fibrations and Markov chains with restart, a particular kind of Markov chains that include the PageRank one as a special case. This fact provides constraints on the...
Graph isomorphism of ordered sets
Heavy subgraph pairs for traceability of block-chains
A graph is called traceable if it contains a Hamilton path, i.e., a path containing all its vertices. Let G be a graph on n vertices. We say that an induced subgraph of G is o−1-heavy if it contains two nonadjacent vertices which satisfy an Ore-type degree condition for traceability, i.e., with degree sum at least n−1 in G. A block-chain is a graph whose block graph is a path, i.e., it is either a P1, P2, or a 2-connected graph, or a graph with at least one cut vertex and exactly two end-blocks....
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.
Isomorphism-induced line isomorphisms on pseudographs
Isomorphisms of Cayley graphs of a free Abelian group.
Join graphs of trees
Kocay's lemma, Whitney's theorem, and some polynomial invariant reconstruction problems.
Locally homogeneous graphs with dense links at vertices
Neighborhoods in line graphs
Nonexistence of triples of nonisomorphic connected graphs with isomorphic connected -graphs.
Non-isomorphic graphs with cospectral symmetric powers.