On Balanced Graphs

Berge defined a hypergraph to be balanced if its incidence matrix is balanced. We consider this concept applied to graphs, and call a graph to be balanced when its clique matrix is balanced. Characterizations of balanced graphs by forbidden subgraphs and by clique subgraphs are proved in this work. Using properties of domination we define four subclasses of balanced graphs. Two of them are characterized by 0–1 matrices and can be recognized in polynomial time. Furthermore, we propose polynomial time combinatorial algorithms for the problems of stable set, clique-independent set and clique-transversal for one of these subclasses of balanced graphs. Finally, we analyse the behavior of balanced graphs and these four subclasses under the clique graph operator. Received: April, 2004     

Transforming a graph into a 1-balanced graph

Let G be a non-trivial, loopless graph and for each non-trivial subgraph H of G, let . The graph G is 1-balanced if γ(G), the maximum among g(H), taken over all non-trivial subgraphs H of G, is attained when H=G. This quantity γ(G) is called the fractional arboricity of the graph G. The value γ(G) appears in a paper by Picard and Queyranne and has been studied extensively by Catlin, Grossman, Hobbs and Lai. The quantity γ(G)−g(G) measures how much a given graph G differs from being 1-balanced. In this paper, we describe a systematic method of modifying a given graph to obtain a 1-balanced graph on the same number of vertices and edges. We obtain this by a sequence of iterations; each iteration re-defining one end-vertex of an edge in the given graph. After each iteration, either the value γ of the new graph formed is less than that of the graph from the previous iteration or the size of the maximal γ-achieving subgraph of the new graph is smaller than that of the graph in the previous iteration. We show that our algorithm is polynomial in time complexity. Further ways to decrease the number of iterations are also discussed.     

太阳图与路的笛卡儿积图的任意可分性（英文）

一个阶为n的图G称为是任意可分的(简作AP),如果对于任一正整数序列τ=(n₁,n₂,…,n_k)满足n=n₁+n₂+…+n_k,总是存在顶点集V(G)的一个划分(V₁,V₂,…,V_k)满足:对于i∈[1,k],|V_i|=n_i,且子图G|V_i|是图G的V_i导出的一个连通子图.我们用S~*=S(n;m₁,m₂,…,m_n)来表示最大度△(S~*)=3的太阳图.本文讨论了图S~*P_m(m≥3)的任意可分性.     

On anti-magic labeling for graph products

An anti-magic labeling of a finite simple undirected graph with p vertices and q edges is a bijection from the set of edges to the set of integers {1,2,…,q} such that the vertex sums are pairwise distinct, where the vertex sum at one vertex is the sum of labels of all edges incident to such vertex. A graph is called anti-magic if it admits an anti-magic labeling. Hartsfield and Ringel conjectured in 1990 that all connected graphs except K₂ are anti-magic. Recently, Alon et al. showed that this conjecture is true for dense graphs, i.e. it is true for p-vertex graphs with minimum degree Ω(logp). In this article, new classes of sparse anti-magic graphs are constructed through Cartesian products and lexicographic products.     

Two-ended regular median graphs

We show that regular median graphs of linear growth are the Cartesian product of finite hypercubes with the two-way infinite path. Such graphs are Cayley graphs and have only two ends.For cubic median graphs G the condition of linear growth can be weakened to the condition that G has two ends. For higher degree the relaxation to two-ended graphs is not possible, which we demonstrate by an example of a median graph of degree four that has two ends, but nonlinear growth.     

关于笛卡尔乘积图的优美性

研究了笛卡尔乘积图Pm×Pn×P1的优美标号算法,并且给出了他们都是优美图的证明,同时推广了笛卡尔乘积图Pm×Pn是优美图的结论.     

Adaptable chromatic number of graph products

A colouring of the vertices of a graph (or hypergraph) G is adapted to a given colouring of the edges of G if no edge has the same colour as both (or all) its vertices. The adaptable chromatic number of G is the smallest integer k such that each edge-colouring of G by colours 1,2,…,k admits an adapted vertex-colouring of G by the same colours 1,2,…,k. (The adaptable chromatic number is just one more than a previously investigated notion of chromatic capacity.) The adaptable chromatic number of a graph G is smaller than or equal to the ordinary chromatic number of G. While the ordinary chromatic number of all (categorical) powers G^k of G remains the same as that of G, the adaptable chromatic number of G^k may increase with k. We conjecture that for all sufficiently large k the adaptable chromatic number of G^k equals the chromatic number of G. When G is complete, we prove this conjecture with k≥4, and offer additional evidence suggesting it may hold with k≥2. We also discuss other products and propose several open problems.     

Connectivity of Cartesian product graphs

Use v_i,κ_i,λ_i,δ_i to denote order, connectivity, edge-connectivity and minimum degree of a graph G_i for i=1,2, respectively. For the connectivity and the edge-connectivity of the Cartesian product graph, up to now, the best results are κ(G₁×G₂)?κ₁+κ₂ and λ(G₁×G₂)?λ₁+λ₂. This paper improves these results by proving that κ(G₁×G₂)?min{κ₁+δ₂,κ₂+δ₁} and λ(G₁×G₂)=min{δ₁+δ₂,λ₁v₂,λ₂v₁} if G₁ and G₂ are connected undirected graphs; κ(G₁×G₂)?min{κ₁+δ₂,κ₂+δ₁,2κ₁+κ₂,2κ₂+κ₁} if G₁ and G₂ are strongly connected digraphs. These results are also generalized to the Cartesian products of connected graphs and n strongly connected digraphs, respectively.     

Characterizing Flag Graphs and Induced Subgraphs of Cartesian Product Graphs

The vertices of the flag graph Φ(P) of a graded poset P are its maximal chains. Two vertices are adjacent whenever two maximal chains differ in exactly one element. In this paper we characterize induced subgraphs of Cartesian product graphs and flag graphs of graded posets. The latter class of graphs lies between isometric and induced subgraphs of Cartesian products in the embedding structure theory. Both characterization use certain edge-labelings of graphs.     

Characterizing subgraphs of Hamming graphs

Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph G is an induced subgraph of a Hamming graph if and only if there exists a labeling of E(G) fulfilling the following two conditions: (i) edges of a triangle receive the same label; (ii) for any vertices u and v at distance at least two, there exist two labels which both appear on any induced u, υ‐path. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 302–312, 2005     

Fair reception and Vizing's conjecture

In this paper we introduce the concept of fair reception of a graph which is related to its domination number. We prove that all graphs G with a fair reception of size γ(G) satisfy Vizing's conjecture on the domination number of Cartesian product graphs, by which we extend the well‐known result of Barcalkin and German concerning decomposable graphs. Combining our concept with a result of Aharoni, Berger and Ziv, we obtain an alternative proof of the theorem of Aharoni and Szabó that chordal graphs satisfy Vizing's conjecture. A new infinite family of graphs that satisfy Vizing's conjecture is also presented. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 45‐54, 2009     

The distinguishing chromatic number of Cartesian products of two complete graphs

A labeling of a graph G is distinguishing if it is only preserved by the trivial automorphism of G. The distinguishing chromatic number of G is the smallest integer k such that G has a distinguishing labeling that is at the same time a proper vertex coloring. The distinguishing chromatic number of the Cartesian product is determined for all k and n. In most of the cases it is equal to the chromatic number, thus answering a question of Choi, Hartke and Kaul whether there are some other graphs for which this equality holds.     

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.     

Cartesian products of directed graphs with loops

We show that every nontrivial finite or infinite connected directed graph with loops and at least one vertex without a loop is uniquely representable as a Cartesian or weak Cartesian product of prime graphs. For finite graphs the factorization can be computed in linear time and space.     

Tight products and graph expansion

In this article, we study a new product of graphs called tight product. A graph H is said to be a tight product of two (undirected multi) graphs G₁ and G₂, if V(H) = V(G₁) × V(G₂) and both projection maps V(H)→V(G₁) and V(H)→V(G₂) are covering maps. It is not a priori clear when two given graphs have a tight product (in fact, it is NP‐hard to decide). We investigate the conditions under which this is possible. This perspective yields a new characterization of class‐1 (2k+ 1)‐regular graphs. We also obtain a new model of random d‐regular graphs whose second eigenvalue is almost surely at most O(d^3/4). This construction resembles random graph lifts, but requires fewer random bits. © 2011 Wiley Periodicals, Inc. J Graph Theory     

On the edge-connectivity and restricted edge-connectivity of a product of graphs

The product graph G_m*G_p of two given graphs G_m and G_p was defined by Bermond et al. [Large graphs with given degree and diameter II, J. Combin. Theory Ser. B 36 (1984) 32-48]. For this kind of graphs we provide bounds for two connectivity parameters (λ and λ^′, edge-connectivity and restricted edge-connectivity, respectively), and state sufficient conditions to guarantee optimal values of these parameters. Moreover, we compare our results with other previous related ones for permutation graphs and cartesian product graphs, obtaining several extensions and improvements. In this regard, for any two connected graphs G_m, G_p of minimum degrees δ(G_m), δ(G_p), respectively, we show that λ(G_m*G_p) is lower bounded by both δ(G_m)+λ(G_p) and δ(G_p)+λ(G_m), an improvement of what is known for the edge-connectivity of G_m×G_p.     

笛卡尔乘积图里的最小k-路点覆盖

对于子集$S\subseteq V(G)$,如果图$G$里的每一条$k$路都至少包含$S$中的一个点,那么我们称集合$S$是图$G$的一个$k$-路点覆盖.很明显,这个子集并不唯一.我们称最小的$k$-路点覆盖的基数为$k$-路点覆盖数, 记作$\psi_k(G)$.本文给出了一些笛卡尔乘积图上$\psi_k(G)$值的上界或下界.     

Prime graphs and exponential composition of species

In this paper, we enumerate prime graphs with respect to the Cartesian multiplication of graphs. We use the unique factorization of a connected graph into the product of prime graphs given by Sabidussi to find explicit formulas for labeled and unlabeled prime graphs. In the case of species, we construct the exponential composition of species based on the arithmetic product of species of Maia and Méndez, and express the species of connected graphs as the exponential composition of the species of prime graphs.     

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.