Computing the eccentric-distance sum for graph operations

In this paper, we present explicit formulas for computing the eccentric-distance sum of the most important graph operations such as the Cartesian product, join, composition, disjunction, symmetric difference, cluster and corona product of graphs. Also, we apply our results to compute this eccentricity-related invariant for some important classes of molecular graphs and nano-structures by specializing components of these graph operations.     

关于图的强乘积的可迁性的研究（英文）

Since many large graphs are composed from some existing smaller graphs by using graph operations, say, the Cartesian product, the Lexicographic product and the Strong product. Many properties of such large graphs are closely related to those of the corresponding smaller ones. In this short note, we give some properties of the Strong product of vertex-transitive graphs. In particular, we show that the Strong product of Cayley graphs is still a Cayley graph.     

Some results on the lexicographic product of vertex-transitive graphs

Many large graphs can be constructed from existing smaller graphs by using graph operations, for example, the Cartesian product and the lexicographic product. Many properties of such large graphs are closely related to those of the corresponding smaller ones. In this short note, we give some properties of the lexicographic products of vertex-transitive and of edge-transitive graphs. In particular, we show that the lexicographic product of Cayley graphs is a Cayley graph.     

Constructing cospectral graphs via a new form of graph product

We present a new method to construct a family of co-spectral graphs. Our method is based on a new type of graph product that we define, the bipartite graph product, which may be of self-interest. Our method is different from existing techniques in the sense that it is not based on a sequence of local graph operations (e.g. Godsil–McKay switching). The explicit nature of our construction allows us, for example, to construct an infinite family of cospectral graphs and provide an easy proof of non-isomorphism. We are also able to characterize fully the spectrum of the cospectral graphs.     

Equistable graphs, general partition graphs, triangle graphs, and graph products

In this paper we examine the connections between equistable graphs, general partition graphs and triangle graphs. While every general partition graph is equistable and every equistable graph is a triangle graph, not every triangle graph is equistable, and a conjecture due to Jim Orlin states that every equistable graph is a general partition graph. The conjecture holds within the class of chordal graphs; if true in general, it would provide a combinatorial characterization of equistable graphs.Exploiting the combinatorial features of triangle graphs and general partition graphs, we verify Orlin’s conjecture for several graph classes, including AT-free graphs and various product graphs. More specifically, we obtain a complete characterization of the equistable graphs that are non-prime with respect to the Cartesian or the tensor product, and provide some necessary and sufficient conditions for the equistability of strong, lexicographic and deleted lexicographic products. We also show that the general partition graphs are not closed under the strong product, answering a question by McAvaney et al.     

Graph operations characterizing rank-width

Graph complexity measures such as tree-width, clique-width and rank-width are important because they yield Fixed Parameter Tractable algorithms. These algorithms are based on hierarchical decompositions of the considered graphs, and on boundedness conditions on the graph operations that, more or less explicitly, recombine the components of decompositions into larger graphs. Rank-width is defined in a combinatorial way, based on a tree, and not in terms of graph operations. We define operations on graphs that characterize rank-width and help for the construction of Fixed Parameter Tractable algorithms, especially for problems specified in monadic second-order logic.     

Graph theoretic approach to parallel gene assembly

We study parallel complexity of signed graphs motivated by the highly complex genetic recombination processes in ciliates. The molecular gene assembly operations have been modeled by operations of signed graphs, i.e., graphs where the vertices have a sign + or −. In the optimization problem for signed graphs one wishes to find the parallel complexity by which the graphs can be reduced to the empty graph. We relate parallel complexity to matchings in graphs for some natural graph classes, especially bipartite graphs. It is shown, for instance, that a bipartite graph G has parallel complexity one if and only if G has a unique perfect matching. We also formulate some open problems of this research topic.     

The hyper-Zagreb index and some graph operations

Let G be a simple connected graph. The Hyper-Zagreb index is defined as \(\textit{HM}(G)=\sum _{uv\in E_{G}}(d_{G}(u)+d_{G}(v))^2\). In this paper some exact expressions for the hyper-Zagreb index of graph operations containing cartesian product and join of n graphs, splice, link and chain of graphs will be presented. We also apply these results to some graphs to chemical and general interest, such as \(C_4\) nanotube, rectangular grid, prism, complete n-partite graph.     

A note on immersion minors and planarity

Graph minors play an important role in graph theory. The focus of this paper is on immersion minors and their relationship to planarity. In general, planar graphs can have non-planar immersion minors. This paper shows that by placing a simple restriction on the immersion-minor operations, all immersion minors of a planar graph are planar. This then allows one to easily obtain a characterization of planar graphs using immersion minors. A dual form of this characterization, as well as an extension to binary matroids, are also considered.     

Complement and Isomorphism on Bipolar Fuzzy Graphs

In this paper, we discuss some properties of the self complement and self weak complement bipolar fuzzy graphs, and get a sufficient condition for a bipolar fuzzy graph to be the self weak complement bipolar fuzzy graph. Also we investigate relations between operations union, join, and complement on bipolar fuzzy graphs.     

Effects on the normalized Laplacian spectral radius of non-bipartite graphs under perturbation and their applications

The normalized Laplacian eigenvalues of a network play an important role in its structural and dynamical aspects associated with the network. In this paper, we consider how the normalized Laplacian spectral radius of a non-bipartite graph behaves by several graph operations. As an example of the application, the smallest normalized Laplacian spectral radius of non-bipartite unicyclic graphs with fixed order is determined.     

Products of unit distance graphs

Some graphs admit drawings in the Euclidean plane (k-space) in such a (natural) way, that edges are represented as line segments of unit length. We say that they have the unit distance property.The influence of graph operations on the unit distance property is discussed. It is proved that the Cartesian product preserves the unit distance property in the Euclidean plane, while graph union, join, tensor product, strong product, lexicographic product and corona do not. It is proved that the Cartesian product preserves the unit distance property also in higher dimensions.     

P4-Reducible Graphs—Class of Uniquely Tree-Representable Graphs

We introduce and characterize a new class of graphs which has a unique tree representation, and which strictly contains the well-known class of cographs. We define three graph operations and show that all the graphs in our class can be constructed from single-vertex graphs by a finite sequence of these operations. Finally, we show that a number of computational problems, including the four classical optimization problems, can be solved efficiently for this new class of graphs.     

Energy and NEPS of graphs

The energy of a graph is the sum of the absolute values of the eigenvalues of the graph. We study the energy of the noncomplete extended p-sum (NEPS) of the graphs, a very general composition of the graphs in which the special case is the product of graphs. We show that the energy of the product of graphs is the product of the energy of graphs, and how this result may be used to construct arbitrarily large families of noncospectral connected graphs having the same number of vertices and the same energy. Further, unlike the product, we show that the energy of any other NEPS of the graphs cannot be represented as a function of the energy of starting graphs.     

Vertex and edge PI indices of Cartesian product graphs

The Padmakar-Ivan (PI) index of a graph G is the sum over all edges uv of G of the number of edges which are not equidistant from u and v. In this paper, the notion of vertex PI index of a graph is introduced. We apply this notion to compute an exact expression for the PI index of Cartesian product of graphs. This extends a result by Klavzar [On the PI index: PI-partitions and Cartesian product graphs, MATCH Commun. Math. Comput. Chem. 57 (2007) 573-586] for bipartite graphs. Some important properties of vertex PI index are also investigated.     

Partial cubes: structures, characterizations, and constructions

Partial cubes are isometric subgraphs of hypercubes. Structures on a graph defined by means of semicubes, and Djokovi?’s and Winkler’s relations play an important role in the theory of partial cubes. These structures are employed in the paper to characterize bipartite graphs and partial cubes of arbitrary dimension. New characterizations are established and new proofs of some known results are given.The operations of Cartesian product and pasting, and expansion and contraction processes are utilized in the paper to construct new partial cubes from old ones. In particular, the isometric and lattice dimensions of finite partial cubes obtained by means of these operations are calculated.     

An edge grafting theorem on the energy of unicyclic and bipartite graphs

The energy of a graph is the sum of the absolute values of the eigenvalues of its adjacency matrix. The edge grafting operation on a graph is certain kind of edge moving between two pendant paths starting from the same vertex. In this paper we show how the graph energy changes under the edge grafting operations on unicyclic and bipartite graphs. We also give some applications of this result on the comparison of graph energies between unicyclic or bipartite graphs.     

Dynamically maintaining split graphs

We present an algorithm that supports operations for modifying a split graph by adding edges or vertices and deleting edges, such that after each modification the graph is repaired to become a split graph in a minimal way. In particular, if the graph is not split after the modification, the algorithm computes a minimal, or if desired even a minimum, split completion or deletion of the modified graph. The motivation for such operations is similar to the motivation for fully dynamic algorithms for particular graph classes. In our case we allow all modifications to the graph and repair, rather than allowing only the modifications that keep the graph split. Fully dynamic algorithms of the latter kind are known for split graphs [L. Ibarra, Fully dynamic algorithms for chordal graphs and split graphs, Technical Report DCS-262-IR, University of Victoria, Canada, 2000].Our results can be used to design linear time algorithms for some recognition and completion problems, where the input is supplied in an on-line fashion.     

The first and second Zagreb indices of some graph operations

In this paper some exact expressions for the first and second Zagreb indices of graph operations containing the Cartesian product, composition, join, disjunction and symmetric difference of graphs will be presented. We apply some of our results to compute the Zagreb indices of arbitrary C₄ tube, C₄ torus and q-multi-walled polyhex nanotorus.     

The (signless) Laplacian spectral radius of unicyclic and bicyclic graphs with <Emphasis Type="Italic">n</Emphasis> vertices and <Emphasis Type="Italic">k</Emphasis> pendant vertices

In this paper, the effects on the signless Laplacian spectral radius of a graph are studied when some operations, such as edge moving, edge subdividing, are applied to the graph. Moreover, the largest signless Laplacian spectral radius among the all unicyclic graphs with n vertices and k pendant vertices is identified. Furthermore, we determine the graphs with the largest Laplacian spectral radii among the all unicyclic graphs and bicyclic graphs with n vertices and k pendant vertices, respectively.