Non-zero component union graph of a finite-dimensional vector space

In this paper, we introduce a graph structure, called non-zero component union graph on finite-dimensional vector spaces. We show that the graph is connected and find its domination number, clique number and chromatic number. It is shown that two non-zero component union graphs are isomorphic if and only if the base vector spaces are isomorphic. In case of finite fields, we study the edge-connectivity and condition under which the graph is Eulerian. Moreover, we provide a lower bound for the independence number of the graph. Finally, we come up with a structural characterization of non-zero component union graph.     

Nonzero Component Graph of a Finite Dimensional Vector Space

In this article, we introduce a graph structure, called a nonzero component graph on finite dimensional vector spaces. We show that the graph is connected and find its domination number and independence number. We also study the inter-relationship between vector space isomorphisms and graph isomorphisms, and it is shown that two graphs are isomorphic if and only if the corresponding vector spaces are so. Finally, we determine the degree of each vertex in case the base field is finite.     

CYCLE SPACES OF GRAPHS ON THE SPHERE AND THE PROJECTIVE PLANE

Cycle base theory of a graph has been well studied in abstract mathematical field such matroid theory as Whitney and Tutte did and found many applications in pratical uses such as electric circuit theory and structure analysis, etc. In this paper graph embedding theory is used to investigate cycle base structures of a 2-(edge)-connected graph on the sphere and the projective plane and it is shown that short cycles do generate the cycle spaces in the case of ““““small face-embeddings““““. As applications the authors find the exact formulae for the minimum lengthes of cycle bases of some types of graphs and present several known results. Infinite examples shows that the conditions in their main results are best possible and there are many 3-connected planar graphs whose minimum cycle bases can not be determined by the planar formulae but may be located by re-embedding them into the projective plane.     

Knot graphs

We consider the equivalence classes of graphs induced by the unsigned versions of the Reidemeister moves on knot diagrams. Any graph that is reducible by some finite sequence of these moves, to a graph with no edges, is called a knot graph. We show that the class of knot graphs strictly contains the set of delta‐wye graphs. We prove that the dimension of the intersection of the cycle and cocycle spaces is an effective numerical invariant of these classes. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 100–111, 2000     

Some transport and diffusion processes on networks and their graph realizability

In this paper we consider systems of transport and diffusion problems on one-dimensional domains coupled through transmission type boundary conditions at the endpoints and determine what types of such problems can be identified with respective problems on metric graphs. For the transport problem the answer is provided by a reformulation of a graph theoretic result characterizing line digraphs of a digraph, whereas in the case of diffusion the answer is provided by an algebraic characterization of matrices which are adjacency matrices of line graphs, which complements known results from graph theory and is particularly suitable for this application.     

On distance subgraphs of graphs in spaces of lower dimensions

This paper studies the problem on the frequency of the event where a graph with a fixed number of vertices contains induced subgraphs that are isomorphic to distance graphs in spaces of definite dimensions. In particular, the case of plane and three-dimensional spaces is considered.     

Optimally reliable networks

In this paper, we consider the probability of disconnection of a graph as a measure of network reliability. We compare the vertex and edge failure cases, and then concentrate on the vertex failure case. Optimal graphs are graphs which minimise the probability of disconnection for a given number of vertices and edges when the probability of vertex failure is small. We describe the known results on the construction of optimal regular graphs and present some new results on the construction of optimal nonregular graphs.     

Zero-divisor graphs of nilpotent-free semigroups

We find strong relationships between the zero-divisor graphs of apparently disparate kinds of nilpotent-free semigroups by introducing the notion of an Armendariz map between such semigroups, which preserves many graph-theoretic invariants. We use it to give relationships between the zero-divisor graph of a ring, a polynomial ring, and the annihilating-ideal graph. Then we give relationships between the zero-divisor graphs of certain topological spaces (so-called pearled spaces), prime spectra, maximal spectra, tensor-product semigroups, and the semigroup of ideals under addition, obtaining surprisingly strong structure theorems relating ring-theoretic and topological properties to graph-theoretic invariants of the corresponding graphs.     

Weakly interacting particle systems on inhomogeneous random graphs

We consider weakly interacting diffusions on time varying random graphs. The system consists of a large number of nodes in which the state of each node is governed by a diffusion process that is influenced by the neighboring nodes. The collection of neighbors of a given node changes dynamically over time and is determined through a time evolving random graph process. A law of large numbers and a propagation of chaos result is established for a multi-type population setting where at each instant the interaction between nodes is given by an inhomogeneous random graph which may change over time. This result covers the setting in which the edge probabilities between any two nodes are allowed to decay to 0 as the size of the system grows. A central limit theorem is established for the single-type population case under stronger conditions on the edge probability function.     

Graph homology: Koszul and Verdier duality

We show that Verdier duality for certain sheaves on the moduli spaces of graphs associated to differential graded operads corresponds to the cobar-duality of operads (which specializes to Koszul duality for Koszul operads). This in particular gives a conceptual explanation of the appearance of graph cohomology of both the commutative and Lie types in computations of the cohomology of the outer automorphism group of a free group. Another consequence is an explicit computation of dualizing sheaves on spaces of metric graphs, thus characterizing to which extent these spaces are different from oriented orbifolds. We also provide a relation between the cohomology of the space of metric ribbon graphs, known to be homotopy equivalent to the moduli space of Riemann surfaces, and the cohomology of a certain sheaf on the space of usual metric graphs.     

On the Hilbert Evolution Algebras of a Graph

Evolution algebras are a special class of nonassociative algebras exhibiting connections with various fields of mathematics. Hilbert evolution algebras generalize the concept in the framework of Hilbert spaces. This allows us to deal with a wide class of infinite-dimensional spaces. We study Hilbert evolution algebras associated to a graph. Inspired by the definitions of evolution algebras we define the Hilbert evolution algebra that is associated to a given graph and the Hilbert evolution algebra that is associated to the symmetric random walk on a graph. For a given graph, we provide the conditions for these structures to be or not to be isomorphic. Our definitions and results extend to the graphs with infinitely many vertices. We also develop a similar theory for the evolution algebras associated to finite graphs.

     

Spectral Characterizations of Some Distance-Regular Graphs

When can one see from the spectrum of a graph whether it is distance-regular or not? We give some new results for when this is the case. As a consequence we find (among others) that the following distance-regular graphs are uniquely determined by their spectrum: The collinearity graphs of the generalized octagons of order (2,1), (3,1) and (4,1), the Biggs-Smith graph, the M ₂₂ graph, and the coset graphs of the doubly truncated binary Golay code and the extended ternary Golay code.     

On the possible values of the entropy of undirected graphs

The entropy of a digraph is a fundamental measure that relates network coding, information theory, and fixed points of finite dynamical systems. In this article, we focus on the entropy of undirected graphs. We prove any bounded interval only contains finitely many possible values of the entropy of an undirected graph. We also determine all the possible values for the entropy of an undirected graph up to the value of four.     

Milnor invariants for spatial graphs

Link-homotopy has been an active area of research for knot theorists since its introduction by Milnor in the 1950s. We introduce a new equivalence relation on spatial graphs called component-homotopy, which reduces to link-homotopy in the classical case. Unlike previous attempts at generalizing link-homotopy to spatial graphs, our new relation allows analogues of some standard link-homotopy results and invariants.In particular we can define a type of Milnor group for a spatial graph under component-homotopy, and this group determines whether or not the spatial graph is splittable. More surprisingly, we will also show that whether the spatial graph is splittable up to component-homotopy depends only on the link-homotopy class of the links contained within it. Numerical invariants of the relation will also be produced.     

On quasi-strongly regular graphs

We study the quasi-strongly regular graphs, which are a combinatorial generalization of the strongly regular and the distance regular graphs. Our main focus is on quasi-strongly regular graphs of grade 2. We prove a “spectral gap”-type result for them which generalizes Seidel's well-known formula for the eigenvalues of a strongly regular graph. We also obtain a number of necessary conditions for the feasibility of parameter sets and some structural results. We propose the heuristic principle that the quasi-strongly regular graphs can be viewed as a “lower-order approximation” to the distance regular graphs. This idea is illustrated by extending a known result from the distance-regular case to the quasi-strongly regular case. Along these lines, we propose a number of conjectures and open problems. Finally, we list the all the proper connected quasi-strongly graphs of grade 2 with up to 12 vertices.     

On quasi-strongly regular graphs

We study the quasi-strongly regular graphs, which are a combinatorial generalization of the strongly regular and the distance regular graphs. Our main focus is on quasi-strongly regular graphs of grade 2. We prove a “spectral gap”-type result for them which generalizes Seidel's well-known formula for the eigenvalues of a strongly regular graph. We also obtain a number of necessary conditions for the feasibility of parameter sets and some structural results. We propose the heuristic principle that the quasi-strongly regular graphs can be viewed as a “lower-order approximation” to the distance regular graphs. This idea is illustrated by extending a known result from the distance-regular case to the quasi-strongly regular case. Along these lines, we propose a number of conjectures and open problems. Finally, we list the all the proper connected quasi-strongly graphs of grade 2 with up to 12 vertices.     

Roundness Properties of Groups

Roundness of metric spaces was introduced by Per Enflo as a tool to study uniform structures of linear topological spaces. The present paper investigates geometric and topological properties detected by the roundness of general metric spaces. In particular, we show that geodesic spaces of roundness 2 are contractible, and that a compact Riemannian manifold with roundness >1 must be simply connected. We then focus our investigation on Cayley graphs of finitely generated groups. One of our main results is that every Cayley graph of a free Abelian group on ⩾ 2 generators has roundness =1. We show that if a group has no Cayley graph of roundness =1, then it must be a torsion group with every element of order 2,3,5, or 7 Partially supported by a Canisius College Summer Research Grant     

Discrete Morse Theory and the Homotopy Type of Clique Graphs

We attach topological concepts to a simple graph by means of the simplicial complex of its complete subgraphs. Using Forman’s discrete Morse theory we show that the strong product of two graphs is homotopic to the topological product of the spaces of their complexes. As a consequence, we enlarge the class of clique divergent graphs known to be homotopy equivalent to all its iterated clique graphs.     

From graphs to ortholattices and equivariant maps

A functor is constructed from the category of graphs and graph homomorphisms to the category of spaces with involutions and equivariant homotopy classes of maps. This can sometimes be used to prove lower bounds on chromatic numbers, and was inspired by Lovász's proof of Kneser's conjecture. Ortholattices occur as an intermediate step between graphs and spaces, and the correspondence between graphs and ortholattices is analyzed.     

On a conjecture of Brouwer involving the connectivity of strongly regular graphs

In this paper, we study a conjecture of Andries E. Brouwer from 1996 regarding the minimum number of vertices of a strongly regular graph whose removal disconnects the graph into non-singleton components.We show that strongly regular graphs constructed from copolar spaces and from the more general spaces called Δ-spaces are counterexamples to Brouwer?s Conjecture. Using J.I. Hall?s characterization of finite reduced copolar spaces, we find that the triangular graphs T(m), the symplectic graphs Sp(2r,q) over the field Fq (for any q prime power), and the strongly regular graphs constructed from the hyperbolic quadrics O⁺(2r,2) and from the elliptic quadrics O⁻(2r,2) over the field F₂, respectively, are counterexamples to Brouwer?s Conjecture. For each of these graphs, we determine precisely the minimum number of vertices whose removal disconnects the graph into non-singleton components. While we are not aware of an analogue of Hall?s characterization theorem for Δ-spaces, we show that complements of the point graphs of certain finite generalized quadrangles are point graphs of Δ-spaces and thus, yield other counterexamples to Brouwer?s Conjecture.We prove that Brouwer?s Conjecture is true for many families of strongly regular graphs including the conference graphs, the generalized quadrangles GQ(q,q) graphs, the lattice graphs, the Latin square graphs, the strongly regular graphs with smallest eigenvalue −2 (except the triangular graphs) and the primitive strongly regular graphs with at most 30 vertices except for few cases.We leave as an open problem determining the best general lower bound for the minimum size of a disconnecting set of vertices of a strongly regular graph, whose removal disconnects the graph into non-singleton components.