On the well-coveredness of Cartesian products of graphs

A graph G is well-covered if every maximal independent set has the same cardinality. This paper investigates when the Cartesian product of two graphs is well-covered. We prove that if G and H both belong to a large class of graphs that includes all non-well-covered triangle-free graphs and most well-covered triangle-free graphs, then G×H is not well-covered. We also show that if G is not well-covered, then neither is G×G. Finally, we show that G×G is not well-covered for all graphs of girth at least 5 by introducing super well-covered graphs and classifying all such graphs of girth at least 5.     

On bipartite distance-regular graphs with a strongly closed subgraph of diameter three

Let Γ denote a distance-regular graph with a strongly closed regular subgraph Y. Hosoya and Suzuki [R. Hosoya, H. Suzuki, Tight distance-regular graphs with respect to subsets, European J. Combin. 28 (2007) 61-74] showed an inequality for the second largest and least eigenvalues of Γ in the case Y is of diameter 2. In this paper, we study the case when Γ is bipartite and Y is of diameter 3, and obtain an inequality for the second largest eigenvalue of Γ. Moreover, we characterize the distance-regular graphs with a completely regular strongly closed subgraph H(3,2).     

Hamiltonicity and pancyclicity of cartesian products of graphs

The cartesian product of a graph G with K₂ is called a prism over G. We extend known conditions for hamiltonicity and pancyclicity of the prism over a graph G to the cartesian product of G with paths, cycles, cliques and general graphs. In particular we give results involving cubic graphs and almost claw-free graphs.We also prove the following: Let G and H be two connected graphs. Let both G and H have a 2-factor. If Δ(G)≤g^′(H) and Δ(H)≤g^′(G) (we denote by g^′(F) the length of a shortest cycle in a 2-factor of a graph F taken over all 2-factorization of F), then G□H is hamiltonian.     

Behzad-Vizing conjecture and Cartesian-product graphs

We prove the following theorem: if the Behzad-Vizing conjecture is true for graphs G and H, then is it true for the Cartesian product G□H.     

Independence and coloring properties of direct products of some vertex-transitive graphs

Let α(G) and χ(G) denote the independence number and chromatic number of a graph G, respectively. Let G×H be the direct product graph of graphs G and H. We show that if G and H are circular graphs, Kneser graphs, or powers of cycles, then α(G×H)=max{α(G)|V(H)|,α(H)|V(G)|} and χ(G×H)=min{χ(G),χ(H)}.     

Balanced and 1-balanced graph constructions

There are several density functions for graphs which have found use in various applications. In this paper, we examine two of them, the first being given by b(G)=|E(G)|/|V(G)|, and the other being given by g(G)=|E(G)|/(|V(G)|−ω(G)), where ω(G) denotes the number of components of G. Graphs for which b(H)≤b(G) for all subgraphs H of G are called balanced graphs, and graphs for which g(H)≤g(G) for all subgraphs H of G are called 1-balanced graphs (also sometimes called strongly balanced or uniformly dense in the literature). Although the functions b and g are very similar, they distinguish classes of graphs sufficiently differently that b(G) is useful in studying random graphs, g(G) has been useful in designing networks with reduced vulnerability to attack and in studying the World Wide Web, and a similar function is useful in the study of rigidity. First we give a new characterization of balanced graphs. Then we introduce a graph construction which generalizes the Cartesian product of graphs to produce what we call a generalized Cartesian product. We show that generalized Cartesian product derived from a tree and 1-balanced graphs are 1-balanced, and we use this to prove that the generalized Cartesian products derived from 1-balanced graphs are 1-balanced.     

Convex domination in the composition and cartesian product of graphs

In this paper we characterize the convex dominating sets in the composition and Cartesian product of two connected graphs. The concepts of clique dominating set and clique domination number of a graph are defined. It is shown that the convex domination number of a composition G[H] of two non-complete connected graphs G and H is equal to the clique domination number of G. The convex domination number of the Cartesian product of two connected graphs is related to the convex domination numbers of the graphs involved.     

On perturbations of almost distance-regular graphs

In this paper we show that certain almost distance-regular graphs, the so-called h-punctually walk-regular graphs, can be characterized through the cospectrality of their perturbed graphs. A graph G with diameter D is called h-punctually walk-regular, for a given h≤D, if the number of paths of length ? between a pair of vertices u,v at distance h depends only on ?. The graph perturbations considered here are deleting a vertex, adding a loop, adding a pendant edge, adding/removing an edge, amalgamating vertices, and adding a bridging vertex. We show that for walk-regular graphs some of these operations are equivalent, in the sense that one perturbation produces cospectral graphs if and only if the others do. Our study is based on the theory of graph perturbations developed by Cvetkovi?, Godsil, McKay, Rowlinson, Schwenk, and others. As a consequence, some new characterizations of distance-regular graphs are obtained.     

Feasibility conditions for the existence of walk-regular graphs

A graph X is walk-regular if the vertex-deleted subgraphs of X all have the same characteristic polynomial. Examples of such graphs are vertex-transitive graphs and distance-regular graphs. We show that the usual feasibility conditions for the existence of a distance-regular graph with a given intersection array can be extended so that they apply to walk-regular graphs. Despite the greater generality, our proofs are more elementary than those usually given for distance-regular graphs. An application to the computation of vertex-transitive graphs is described.     

Dominating direct products of graphs

An upper bound for the domination number of the direct product of graphs is proved. It in particular implies that for any graphs G and H, γ(G×H)?3γ(G)γ(H). Graphs with arbitrarily large domination numbers are constructed for which this bound is attained. Concerning the upper domination number we prove that Γ(G×H)?Γ(G)Γ(H), thus confirming a conjecture from [R. Nowakowski, D.F. Rall, Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16 (1996) 53-79]. Finally, for paired-domination of direct products we prove that γ_pr(G×H)?γ_pr(G)γ_pr(H) for arbitrary graphs G and H, and also present some infinite families of graphs that attain this bound.     

On almost distance-regular graphs

Distance-regular graphs are a key concept in Algebraic Combinatorics and have given rise to several generalizations, such as association schemes. Motivated by spectral and other algebraic characterizations of distance-regular graphs, we study ‘almost distance-regular graphs’. We use this name informally for graphs that share some regularity properties that are related to distance in the graph. For example, a known characterization of a distance-regular graph is the invariance of the number of walks of given length between vertices at a given distance, while a graph is called walk-regular if the number of closed walks of given length rooted at any given vertex is a constant. One of the concepts studied here is a generalization of both distance-regularity and walk-regularity called m-walk-regularity. Another studied concept is that of m-partial distance-regularity or, informally, distance-regularity up to distance m. Using eigenvalues of graphs and the predistance polynomials, we discuss and relate these and other concepts of almost distance-regularity, such as their common generalization of (?,m)-walk-regularity. We introduce the concepts of punctual distance-regularity and punctual walk-regularity as a fundament upon which almost distance-regular graphs are built. We provide examples that are mostly taken from the Foster census, a collection of symmetric cubic graphs. Two problems are posed that are related to the question of when almost distance-regular becomes whole distance-regular. We also give several characterizations of punctually distance-regular graphs that are generalizations of the spectral excess theorem.     

Lower bounds for the domination number and the total domination number of direct product graphs

A sharp lower bound for the domination number and the total domination number of the direct product of finitely many complete graphs is given: . Sharpness is established in the case when the factors are large enough in comparison to the number of factors. The main result gives a lower bound for the domination (and the total domination) number of the direct product of two arbitrary graphs: γ(G×H)≥γ(G)+γ(H)−1. Infinite families of graphs that attain the bound are presented. For these graphs it also holds that γ_t(G×H)=γ(G)+γ(H)−1. Some additional parallels with the total domination number are made.     

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.     

Spectra of coronae

We introduce a new invariant, the coronal of a graph, and use it to compute the spectrum of the corona G°H of two graphs G and H. In particular, we show that this spectrum is completely determined by the spectra of G and H and the coronal of H. Previous work has computed the spectrum of a corona only in the case that H is regular. We then explicitly compute the coronals for several families of graphs, including regular graphs, complete n-partite graphs, and paths. Finally, we use the corona construction to generate many infinite families of pairs of cospectral graphs.     

Distance-regular graphs and (s,c, a,k)-graphs

A diameter-bound theorem for a class of distance-regular graphs which includes all those with even girth is presented. A new class of graphs, called (s, c, a, k)-graphs, is introduced, which are conjectured to contain enough of the local structure of finite distance-regular graphs for them all to be finite. It is proved that they are finite and a bound on the diameter is given in the case a ≤ c.     

Geometric aspects of 2-walk-regular graphs

A t-walk-regular graph is a graph for which the number of walks of given length between two vertices depends only on the distance between these two vertices, as long as this distance is at most t. Such graphs generalize distance-regular graphs and t-arc-transitive graphs. In this paper, we will focus on 1- and in particular 2-walk-regular graphs, and study analogues of certain results that are important for distance-regular graphs. We will generalize Delsarte?s clique bound to 1-walk-regular graphs, Godsil?s multiplicity bound and Terwilliger?s analysis of the local structure to 2-walk-regular graphs. We will show that 2-walk-regular graphs have a much richer combinatorial structure than 1-walk-regular graphs, for example by proving that there are finitely many non-geometric 2-walk-regular graphs with given smallest eigenvalue and given diameter (a geometric graph is the point graph of a special partial linear space); a result that is analogous to a result on distance-regular graphs. Such a result does not hold for 1-walk-regular graphs, as our construction methods will show.     

On the Pancyclicity of Lexicographic Products

We prove that if G and H are graphs containing at least one edge each, then their lexicographic product G[H] is weakly pancyclic, i. e., it contains a cycle of every length between the length of a shortest cycle and that of a longest one. This supports some conjectures on locally connected graphs and on product graphs. We obtain an analogous result on even cycles in products G[H] that are bipartite. We also investigate toughness conditions on G implying that G[H] is hamiltonian (and hence pancyclic). Supported by the project LN00A056 of the Czech Ministry of Education     

On a paper of lake about infinite graphs

Lake has constructed graphs G and H such that H contains n disjoint subgraphs isomorphic to G for each positive integer n but H does not contain infinitely many disjoint subgraphs isomorphic to G. Here a concrete example of such graphs with H the lattice points of the plane is given.     

Join of two graphs admits a nowhere-zero 3-flow

Let G be a graph, and λ the smallest integer for which G has a nowherezero λ-flow, i.e., an integer λ for which G admits a nowhere-zero λ-flow, but it does not admit a (λ ? 1)-flow. We denote the minimum flow number of G by Λ(G). In this paper we show that if G and H are two arbitrary graphs and G has no isolated vertex, then Λ(G ∨ H) ? 3 except two cases: (i) One of the graphs G and H is K ₂ and the other is 1-regular. (ii) H = K ₁ and G is a graph with at least one isolated vertex or a component whose every block is an odd cycle. Among other results, we prove that for every two graphs G and H with at least 4 vertices, Λ(G ∨ H) ? 3.