Stable and semi-stable unicyclic graphs

We show by a constructive proof, that if a unicyclic graph has a transposition in its automorphism group, then it is stable. Using a similar technique, we also determine which unicyclic graphs are not semi-stable.     

Embeddings of cartesian products of nearly bipartite graphs

Surgical techniques are often effective in constructing genus embeddings of cartesian products of bipartite graphs. In this paper we present a general construction that is “close” to a genus embedding for cartesian products, where each factor is “close” to being bipartite. In specializing this to repeated cartesian products of odd cycles, we are able to obtain asymptotic results in connection with the genus parameter for finite abelian groups.     

若干图的卡氏积的距离谱和距离能量(英文)

G是顶点集为{v_1,v_2,…,v_n}的连通简单图,G_1,G_2,…,G_n是有限图。联并图G[G_1,G_2,…,G_n】是按如下方式在G_1UG_2U…UG_n上加边而成的图:在G_i和G_j之间的任何两个顶点间加边,若v_i和v_j在G中相邻.[7]给出了两个距离正则图的卡氏积的距离谱.本文计算了联并图和距离正则图的卡氏积及两个联并图的卡氏积的距离谱.在此基础之上,我们得到了两个利用联并图与非同谱距离正则等能量图作卡氏积及联并图作卡氏积构造非同谱等距离能量图族的方法.     

The class of co-Namioka compact spaces is stable under product

In an earlier paper we have established that the cartesian product of a family of co-Namioka compact spaces is co-Namioka if and only if all finite cartesian products of this family are co-Namioka. The purpose of this note is to show that the product of two co-Namioka compact spaces is always co-Namioka. The class of co-Namioka compact spaces is consequently stable under arbitrary products.

     

Isometric embedding in products of complete graphs

An isometric (i.e., distance-preserving) embedding of a connected graph G into a cartesian product of complete graphs is equivalent to a labelling of each vertex of G by a string of symbols of fixed length such that the distance between two vertices is equal to the Hamming distance between the corresponding strings. Such a labelling could provide an addressing scheme for a communications network, since it enables a message to find a shortest path to its destination using only local information.We show that any two such embeddings of the same graph G are essentially the same, and give a polynomial-time algorithm which will find such an embedding if it exists. In addition we characterize the graphs which are isometrically embeddable in powers of K₃.     

Excess in critical graphs

In this paper we prove that the cartesian product of two trees is a semistable graph and we exhibit several vertices of semistability. We show that in most cases the cartesian product of two paths is completely semistable and we list the exceptions. Finally, we characterize stable composite graphs.     

Strict refinement for graphs and digraphs

We show that any two cartesian factorizations of a connected graph have a strict common refinement, improving on the unique factorization theorem of G. Sabidussi. (The cartesian product is the product wherein two vertices are adjacent when they are adjacent in one coordinate and equal in all other coordinates.) Among the applications, we can deduce the strict refinement theorem for chain-finite posets, and (using a cartesian factorization algorithm of P. Winkler) we give a polynomial-time algorithm for cardinal factorization of connected finite posets.     

s-strongly perfect cartesian product of graphs

The study of perfectness, via the strong perfect graph conjecture, has given rise to numerous investigations concerning the structure of many particular classes of perfect graphs. In “Perfect Product Graphs” (Discrete Mathematics, Vol. 20, 1977, pp. 177--186), G. Ravindra and K. R. Parthasarathy tried, but unfortunately without success, to characterize the perfectness of the cartesian product of graphs (see also MR No. 58--10567, 1979). In this paper we completely characterize the graphs that are both nontrivial cartesian products and s-strongly perfect.     

3‐Factor‐Criticality of Vertex‐Transitive Graphs

A graph of order n is p ‐factor‐critical, where p is an integer of the same parity as n, if the removal of any set of p vertices results in a graph with a perfect matching. 1‐factor‐critical graphs and 2‐factor‐critical graphs are factor‐critical graphs and bicritical graphs, respectively. It is well known that every connected vertex‐transitive graph of odd order is factor‐critical and every connected nonbipartite vertex‐transitive graph of even order is bicritical. In this article, we show that a simple connected vertex‐transitive graph of odd order at least five is 3‐factor‐critical if and only if it is not a cycle.     

A polynomial time algorithm for finding the prime factors of cartesian-product graphs

We consider the computational complexity of recognizinf concerned cartesian product graphs. Sabidussi gives a non-algorithmic proof that the cartesian factorization is unique. He uses a tower of successively coarser equivalence relations on the edge set in which each prime factor of the graph is identified with an equivalence class in the coarsest of the relations. We first explore the structure and size of the relation at the base of the tower. Then we give a polynomial-time algorithm to compute the relations and to construct the prime factors of any connected graph. The bounds on the size of the relations are crucial to the runtime analysis of our algorithm.     

Completely connected clustered graphs

Planar drawings of clustered graphs are considered. We introduce the notion of completely connected clustered graphs, i.e., hierarchically clustered graphs that have the property that not only every cluster but also each complement of a cluster induces a connected subgraph. As a main result, we prove that a completely connected clustered graph is c-planar if and only if the underlying graph is planar. Further, we investigate the influence of the root of the inclusion tree to the choice of the outer face of the underlying graph and vice versa.     

Edge-transitive products

This paper concerns finite, edge-transitive direct and strong products, as well as infinite weak Cartesian products. We prove that the direct product of two connected, non-bipartite graphs is edge-transitive if and only if both factors are edge-transitive and at least one is arc-transitive, or one factor is edge-transitive and the other is a complete graph with loops at each vertex. Also, a strong product is edge-transitive if and only if all factors are complete graphs. In addition, a connected, infinite non-trivial Cartesian product graph G is edge-transitive if and only if it is vertex-transitive and if G is a finite weak Cartesian power of a connected, edge- and vertex-transitive graph H, or if G is the weak Cartesian power of a connected, bipartite, edge-transitive graph H that is not vertex-transitive.     

Compatible connectedness in graphs and topological spaces

A topology on the vertex set of a graphG iscompatible with the graph if every induced subgraph ofG is connected if and only if its vertex set is topologically connected. In the case of locally finite graphs with a finite number of components, it was shown in [11] that a compatible topology exists if and only if the graph is a comparability graph and that all such topologies are Alexandroff. The main results of Section 1 extend these results to a much wider class of graphs. In Section 2, we obtain sufficient conditions on a graph under which all the compatible topologies are Alexandroff and in the case of bipartite graphs we show that this condition is also necessary.     

Peg solitaire on graphs

There have been several papers on the subject of traditional peg solitaire on different boards. However, in this paper we consider a generalization of the game to arbitrary boards. These boards are treated as graphs in the combinatorial sense. We present necessary and sufficient conditions for the solvability of several well-known families of graphs. In the major result of this paper, we show that the cartesian product of two solvable graphs is likewise solvable. Several related results are also presented. Finally, several open problems related to this study are given.     

The integral graphs with index 3 and exactly two main eigenvalues

A graph is called integral if the spectrum of its adjacency matrix has only integral eigenvalues. An eigenvalue of a graph is called main eigenvalue if it has an eigenvector such that the sum of whose entries is not equal to zero. In this paper, we show that there are exactly 25 connected integral graphs with exactly two main eigenvalues and index 3.     

Two applications of semi-stable graphs

A Michigan graph G on a vertex set V is called semi-stable if for some υ?V, Γ(G_υ) = Γ(G)_υ. It can be shown that all regular graphs are semi-stable and this fact is used to show (i) that if Γ(G) is doubly transitive then G = K_n or K?_n, and (ii) that Γ(G) can be recovered from Γ(G_υ). The second result is extended to the case of stable graphs.     

Conditions on Ramsey Nonequivalence

Given a graph H , a graph G is called a Ramsey graph of H if there is a monochromatic copy of H in every coloring of the edges of G with two colors. Two graphs G , H are called Ramsey equivalent if they have the same set of Ramsey graphs. Fox et al. (J Combin Theory Ser B 109 (2014), 120–133) asked whether there are two nonisomorphic connected graphs that are Ramsey equivalent. They proved that a clique is not Ramsey equivalent to any other connected graph. Results of Ne?et?il et al. showed that any two graphs with different clique number (Combinatorica 1(2) (1981), 199–202) or different odd girth (Comment Math Univ Carolin 20(3) (1979), 565–582) are not Ramsey equivalent. These are the only structural graph parameters we know that “distinguish” two graphs in the above sense. This article provides further supportive evidence for a negative answer to the question of Fox et al. by claiming that for wide classes of graphs, the chromatic number is a distinguishing parameter. In addition, it is shown here that all stars and paths and all connected graphs on at most five vertices are not Ramsey equivalent to any other connected graph. Moreover, two connected graphs are not Ramsey equivalent if they belong to a special class of trees or to classes of graphs with clique‐reduction properties.     

The vertex isoperimetric problem for the powers of the diamond graph

We introduce a new graph for all whose cartesian powers the vertex isoperimetric problem has nested solutions. This is the fourth kind of graphs with this property besides the well-studied graphs like hypercubes, grids, and tori. In contrast to the mentioned graphs, our graph is not bipartite. We present an exact solution to the vertex isoperimetric problem on our graph by introducing a new class of orders that unifies all known isoperimetric orders defined on the cartesian powers of graphs.     

A natural graph of finite fields distinguishing between models

We define a graph structure associated in a natural way to finite fields that nevertheless distinguishes between different models of isomorphic fields. Certain basic notions in finite field theory have interpretations in terms of standard graph properties. We show that the graphs are connected and provide an estimate of their diameter. An accidental graph isomorphism is uncovered and proved. The smallest non-trivial Laplace eigenvalue is given some attention, in particular for a specific family of 8-regular graphs showing that it is not an expander. We introduce a regular covering graph and show that it is connected if and only if the root is primitive.     

On the spanning tree packing number of a graph: a survey

The spanning tree packing number or STP number of a graph G is the maximum number of edge-disjoint spanning trees contained in G. We use an observation of Paul Catlin to investigate the STP numbers of several families of graphs including quasi-random graphs, regular graphs, complete bipartite graphs, cartesian products and the hypercubes.