On the domination number of the cartesian product of the cycle of length n and any graph

Let γ(G) denote the domination number of a graph G and let C_n□G denote the cartesian product of C_n, the cycle of length n?3, and G. In this paper, we are mainly concerned with the question: which connected nontrivial graphs satisfy γ(C_n□G)=γ(C_n)γ(G)? We prove that this equality can only hold if n≡1 (mod 3). In addition, we characterize graphs which satisfy this equality when n=4 and provide infinite classes of graphs for general n≡1 (mod 3).     

On the 2-rainbow domination in graphs

The concept of 2-rainbow domination of a graph G coincides with the ordinary domination of the prism G□K₂. In this paper, we show that the problem of deciding if a graph has a 2-rainbow dominating function of a given weight is NP-complete even when restricted to bipartite graphs or chordal graphs. Exact values of 2-rainbow domination numbers of several classes of graphs are found, and it is shown that for the generalized Petersen graphs GP(n,k) this number is between ⌈4n/5⌉ and n with both bounds being sharp.     

图的符号团边控制数

本文研究了图的符号团边控制数的问题.利用鸽巢原理,获得了图K_n∨P_m和K_n∨C_m的符号团边控制数,推广了已有的结果.     

Non-cover generalized Mycielski, Kneser, and Schrijver graphs

A graph is said to be a cover graph if it is the underlying graph of the Hasse diagram of a finite partially ordered set. We prove that the generalized Mycielski graphs M_m(C_2t+1) of an odd cycle, Kneser graphs KG(n,k), and Schrijver graphs SG(n,k) are not cover graphs when m?0,t?1, k?1, and n?2k+2. These results have consequences in circular chromatic number.     

New results on the energy of integral circulant graphs

Circulant graphs are an important class of interconnection networks in parallel and distributed computing. Integral circulant graphs play an important role in modeling quantum spin networks supporting the perfect state transfer as well. The integral circulant graph ICG_n(D) has the vertex set Z_n = {0, 1, 2, … , n − 1} and vertices a and b are adjacent if gcd(a − b, n) ∈ D, where D ⊆ {d : d∣n, 1 ? d < n}. These graphs are highly symmetric, have integral spectra and some remarkable properties connecting chemical graph theory and number theory. The energy of a graph was first defined by Gutman, as the sum of the absolute values of the eigenvalues of the adjacency matrix. Recently, there was a vast research for the pairs and families of non-cospectral graphs having equal energies. Following Bapat and Pati [R.B. Bapat, S. Pati, Energy of a graph is never an odd integer, Bull. Kerala Math. Assoc. 1 (2004) 129-132], we characterize the energy of integral circulant graph modulo 4. Furthermore, we establish some general closed form expressions for the energy of integral circulant graphs and generalize some results from Ili? [A. Ili?, The energy of unitary Cayley graphs, Linear Algebra Appl. 431 (2009), 1881-1889]. We close the paper by proposing some open problems and characterizing extremal graphs with minimal energy among integral circulant graphs with n vertices, provided n is even.     

Fault-tolerant edge and vertex pancyclicity in alternating group graphs

In [J.-M. Chang, J.-S. Yang. Fault-tolerant cycle-embedding in alternating group graphs, Appl. Math. Comput. 197 (2008) 760-767] the authors claim that every alternating group graph AG_n is (n − 4)-fault-tolerant edge 4-pancyclic. Which means that if the number of faults ∣F∣ ? n − 4, then every edge in AG_n − F is contained in a cycle of length ?, for every 4 ? ? ? n!/2 − ∣F∣. They also claim that AG_n is (n − 3)-fault-tolerant vertex pancyclic. Which means that if ∣F∣ ? n − 3, then every vertex in AG_n − F is contained in a cycle of length ?, for every 3 ? ? ? n!/2 − ∣F∣. Their proofs are not complete. They left a few important things unexplained. In this paper we fulfill these gaps and present another proofs that AG_n is (n − 4)-fault-tolerant edge 4-pancyclic and (n − 3)-fault-tolerant vertex pancyclic.     

The graphs with only self-dual signings

Given a graph G, it is possible to attach positive and negative signs to its lines only, to its points only, or to both. The resulting structures are called respectively signed graphs, marked graphs and nets. The dual of each such structure is obtained by changing every sign in it. We determine all graphs G for which every suitable marked graph on G is self-dual (the M-dual graphs), and also the corresponding graphs G for signed graphs (S-dual) and for nets (N-dual.A graph G is M-dual if and only if G or ? is one of the graphs K_2m, 2K_m, mK₂, K_m + K₂ or 2C₄. The S-dual graphs are C₆, 2C₃, 2C₄, 2K_1n, 2nK₂, K_1,2n, nK_1,2, K_2n, K?_n and all graphs obtained from these by the addition of isolated points. Finally, the only N-dual graph other than -K_2n is 2K₂.     

Mutually independent bipanconnected property of hypercube

A graph is denoted by G with the vertex set V(G) and the edge set E(G). A path P = 〈v₀, v₁, … , v_m〉 is a sequence of adjacent vertices. Two paths with equal length P₁ = 〈 u₁, u₂, … , u_m〉 and P₂ = 〈 v₁, v₂, … , v_m〉 from a to b are independent if u₁ = v₁ = a, u_m = v_m = b, and u_i ≠ v_i for 2 ? i ? m − 1. Paths with equal length from a to b are mutually independent if they are pairwisely independent. Let u and v be two distinct vertices of a bipartite graph G, and let l be a positive integer length, d_G(u, v) ? l ? ∣V(G) − 1∣ with (l − d_G(u, v)) being even. We say that the pair of vertices u, v is (m, l)-mutually independent bipanconnected if there exist m mutually independent paths with length l from u to v. In this paper, we explore yet another strong property of the hypercubes. We prove that every pair of vertices u and v in the n-dimensional hypercube, with d_Qn(u,v)?n-1, is (n − 1, l)-mutually independent bipanconnected for every with (l-d_Qn(u,v)) being even. As for d_Qn(u,v)?n-2, it is also (n − 1, l)-mutually independent bipanconnected if l?d_Qn(u,v)+2, and is only (l, l)-mutually independent bipanconnected if l=d_Qn(u,v).     

Bipanconnectivity of faulty hypercubes with minimum degree

In this paper, we consider the conditionally faulty hypercube Q_n with n ? 2 where each vertex of Q_n is incident with at least m fault-free edges, 2 ? m ? n − 1. We shall generalize the limitation m ? 2 in all previous results of edge-bipancyclicity. We also propose a new edge-fault-tolerant bipanconnectivity called k-edge-fault-tolerant bipanconnectivity. A bipartite graph is k-edge-fault-tolerant bipanconnected if G − F remains bipanconnected for any F ⊂ E(G) with ∣F∣ ? k. For every integer m, under the same hypothesis, we show that Q_n is (n − 2)-edge-fault-tolerant edge-bipancyclic and bipanconnected, and the results are optimal with respect to the number of edge faults tolerated. This not only improves some known results on edge-bipancyclicity and bipanconnectivity of hypercubes, but also simplifies the proof.     

Rank numbers of grid graphs

A ranking of a graph is a labeling of the vertices with positive integers such that any path between vertices of the same label contains a vertex of greater label. The rank number of a graph is the smallest possible number of labels in a ranking. We find rank numbers of the Möbius ladder, K_s×P_n, and P₃×P_n. We also find bounds for rank numbers of general grid graphs P_m×P_n.     

Laplacian integral graphs in S(a, b)

Let G_n,m be the family of graphs with n vertices and m edges, when n and m are previously given. It is well-known that there is a subset of G_n,m constituted by graphs G such that the vertex connectivity, the edge connectivity, and the minimum degree are all equal. In this paper, S(a, b)-classes of connected (a, b)-linear graphs with n vertices and m edges are described, where m is given as a function of a,b∈N/2. Some of them have extremal graphs for which the equalities above are extended to algebraic connectivity. These graphs are Laplacian integral although they are not threshold graphs. However, we do build threshold graphs in S(a, b).     

Roman domination in regular graphs

A Roman domination function on a graph G=(V(G),E(G)) is a function f:V(G)→{0,1,2} satisfying the condition that every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=2. The weight of a Roman dominating function is the value f(V(G))=∑_u∈V(G)f(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G. Cockayne et al. [E. J. Cockayne et al. Roman domination in graphs, Discrete Mathematics 278 (2004) 11-22] showed that γ(G)≤γ_R(G)≤2γ(G) and defined a graph G to be Roman if γ_R(G)=2γ(G). In this article, the authors gave several classes of Roman graphs: P_3k,P_3k+2,C_3k,C_3k+2 for k≥1, K_m,n for min{m,n}≠2, and any graph G with γ(G)=1; In this paper, we research on regular Roman graphs and prove that: (1) the circulant graphs and , n⁄≡1 (mod (2k+1)), (n≠2k) are Roman graphs, (2) the generalized Petersen graphs P(n,2k+1)( (mod 4) and ), P(n,1) (n⁄≡2 (mod 4)), P(n,3) ( (mod 4)) and P(11,3) are Roman graphs, and (3) the Cartesian product graphs are Roman graphs.     

Hamiltonian path saturated graphs with small size

A graph G is said to be hamiltonian path saturated (HPS for short), if G has no hamiltonian path but any addition of a new edge in G creates a hamiltonian path in G. It is known that an HPS graph of order n has size at most and, for n?6, the only HPS graph of order n and size is K_n-1∪K₁. Denote by sat(n,HP) the minimum size of an HPS graph of order n. We prove that sat(n,HP)?⌊(3n-1)/2⌋-2. Using some properties of Isaacs’ snarks we give, for every n?54, an HPS graph G_n of order n and size ⌊(3n-1)/2⌋. This proves sat(n,HP)?⌊(3n-1)/2⌋ for n?54. We also consider m-path cover saturated graphs and P_m-saturated graphs with small size.     

Some notes on graphs whose index is close to 2

We consider two classes of graphs: (i) trees of order n and diameter d =n − 3 and (ii) unicyclic graphs of order n and girth g = n − 2. Assuming that each graph within these classes has two vertices of degree 3 at distance k, we order by the index (i.e. spectral radius) the graphs from (i) for any fixed k (1 ? k ? d − 2), and the graphs from (ii) independently of k.     

On the total domination number of cross products of graphs

We give lower and upper bounds on the total domination number of the cross product of two graphs, γ_t(G×H). These bounds are in terms of the total domination number and the maximum degree of the factors and are best possible. We further investigate cross products involving paths and cycles. We determine the exact values of γ_t(G×Pn) and γ_t(C_n×C_m) where P_n and C_n denote, respectively, a path and a cycle of length n.     

Variations of Y-dominating functions on graphs

Let Y be a subset of real numbers. A Y-dominating function of a graph G=(V,E) is a function f:V→Y such that for all vertices v∈V, where N_G[v]={v}∪{u|(u,v)∈E}. Let for any subset S of V and let f(V) be the weight of f. The Y-domination problem is to find a Y-dominating function of minimum weight for a graph G=(V,E). In this paper, we study the variations of Y-domination such as {k}-domination, k-tuple domination, signed domination, and minus domination for some classes of graphs. We give formulas to compute the {k}-domination, k-tuple domination, signed domination, and minus domination numbers of paths, cycles, n-fans, n-wheels, n-pans, and n-suns. Besides, we present a unified approach to these four problems on strongly chordal graphs. Notice that trees, block graphs, interval graphs, and directed path graphs are subclasses of strongly chordal graphs. This paper also gives complexity results for the problems on doubly chordal graphs, dually chordal graphs, bipartite planar graphs, chordal bipartite graphs, and planar graphs.     

Multi-degree reduction of tensor product Bézier surfaces with general boundary constraints

We propose an efficient approach to the problem of multi-degree reduction of rectangular Bézier patches, with prescribed boundary control points. We observe that the solution can be given in terms of constrained bivariate dual Bernstein polynomials. The complexity of the method is O(mn₁n₂) with m ? min(m₁, m₂), where (n₁, n₂) and (m₁, m₂) is the degree of the input and output Bézier surface, respectively. If the approximation—with appropriate boundary constraints—is performed for each patch of several smoothly joined rectangular Bézier surfaces, the result is a composite surface of global C^r continuity with a prescribed r ? 0. In the detailed discussion, we restrict ourselves to r ∈ {0, 1}, which is the most important case in practical application. Some illustrative examples are given.     

A note on domination, girth and minimum degree

Let G be a graph of order n, minimum degree δ?2, girth g?5 and domination number γ. In 1990 Brigham and Dutton [Bounds on the domination number of a graph, Q. J. Math., Oxf. II. Ser. 41 (1990) 269-275] proved that γ?⌈n/2-g/6⌉. This result was recently improved by Volkmann [Upper bounds on the domination number of a graph in terms of diameter and girth, J. Combin. Math. Combin. Comput. 52 (2005) 131-141; An upper bound for the domination number of a graph in terms of order and girth, J. Combin. Math. Combin. Comput. 54 (2005) 195-212] who for i∈{1,2} determined a finite set of graphs G_i such that γ?⌈n/2-g/6-(3i+3)/6⌉ unless G is a cycle or G∈G_i.Our main result is that for every i∈N there is a finite set of graphs G_i such that γ?n/2-g/6-i unless G is a cycle or G∈G_i. Furthermore, we conjecture another improvement of Brigham and Dutton's bound and prove a weakened version of this conjecture.     

The equivariant topology of stable Kneser graphs

The stable Kneser graph SG_n,k, n?1, k?0, introduced by Schrijver (1978) [19], is a vertex critical graph with chromatic number k+2, its vertices are certain subsets of a set of cardinality m=2n+k. Björner and de Longueville (2003) [5] have shown that its box complex is homotopy equivalent to a sphere, Hom(K₂,SG_n,k)?Sk. The dihedral group D2m acts canonically on SG_n,k, the group C₂ with 2 elements acts on K₂. We almost determine the (C₂×D2m)-homotopy type of Hom(K₂,SG_n,k) and use this to prove the following results.The graphs SG_2s,4 are homotopy test graphs, i.e. for every graph H and r?0 such that Hom(SG_2s,4,H) is (r−1)-connected, the chromatic number χ(H) is at least r+6.If k∉{0,1,2,4,8} and n?N(k) then SG_n,k is not a homotopy test graph, i.e. there are a graph G and an r?1 such that Hom(SG_n,k,G) is (r−1)-connected and χ(G)<r+k+2.