The partition dimension of circulant graphs

Let Π = {S₁, S₂, . . . , S_k} be an ordered partition of the vertex set V (G) of a graph G. The partition representation of a vertex v ∈ V (G) with respect to Π is the k-tuple r(v|Π) = (d(v, S₁), d(v, S₂), . . . , d(v, S_k)), where d(v, S) is the distance between v and a set S. If for every pair of distinct vertices u, v ∈ V (G), we have r(u|Π) ≠ r(v|Π), then Π is a resolving partition and the minimum cardinality of a resolving partition of V (G) is called the partition dimension of G. We study the partition dimension of circulant graphs, which are Cayley graphs of cyclic groups. Grigorious et al. [On the partition dimension of circulant graphs] proved that pd(C_n(1, 2, . . . , t)) ≥ t + 1 for n ≥ 3. We disprove this statement by showing that if t ≥ 4 is even, then there exists an infinite set of values of n, such that . We also present exact values of the partition dimension of circulant graphs with 3 generators.     

On the toughness index of planar graphs

The toughness indexτ(G) of a graph G is defined to be the largest integer t such that for any S ? V(G) with |S| > t, c(G - S) < |S| - t, where c(G - S) denotes the number of components of G - S. In particular, 1-tough graphs are exactly those graphs for which τ(G) ≥ 0. In this paper, it is shown that if G is a planar graph, then τ(G) ≥ 2 if and only if G is 4-connected. This result suggests that there may be a polynomial-time algorithm for determining whether a planar graph is 1-tough, even though the problem for general graphs is NP-hard. The result can be restated as follows: a planar graph is 4-connected if and only if it remains 1-tough whenever two vertices are removed. Hence it establishes a weakened version of a conjecture, due to M. D. Plummer, that removing 2 vertices from a 4-connected planar graph yields a Hamiltonian graph.     

Constrained Ramsey numbers of graphs

Given two graphs G and H, let f(G,H) denote the minimum integer n such that in every coloring of the edges of K_n, there is either a copy of G with all edges having the same color or a copy of H with all edges having different colors. We show that f(G,H) is finite iff G is a star or H is acyclic. If S and T are trees with s and t edges, respectively, we show that 1+s(t?2)/2≤f(S,T)≤(s?1)(t²+3t). Using constructions from design theory, we establish the exact values, lying near (s?1)(t?1), for f(S,T) when S and T are certain paths or star‐like trees. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 1–16, 2003     

Distances in Sierpiński graphs and on the Sierpiński gasket

The well known planar fractal called the Sierpiński gasket can be defined with the help of a related sequence of graphs {G _n } _{n ≥ 0}, where G _n is the n-th Sierpiński graph, embedded in the Euclidean plane. In the present paper we prove geometric criteria that allow us to decide, whether a shortest path between two distinct vertices x and y in G _n , that lie in two neighbouring elementary triangles (of the same level), goes through the common vertex of the triangles or through two distinct vertices (both distinct from the common vertex) of those triangles. We also show criteria for the analogous problem on the planar Sierpiński gasket and in the 3-dimensional Euclidean space.     

A Mengerian theorem for paths of length at least three

Let be x, y two vertices of a graph G, such that t openly disjoint xy-paths of length ≥3 exist. In this article we show that then there exists a set S of cardinality less than or equal to 3t – 2, resp. 2t for t ∈ {1, 2, 3}, which destroys all xy-paths of length ≥3. Also a lower bound for the cardinality of S is given by constructing special graphs.     

On the Evaluation of the Tutte Polynomial at the Points (1, –1) and (2, –1)

Motivated by the identity t (K _n+2; 1, –1) = t (K _n ; 2, –1), where t(G; x, y) is the Tutte polynomial of a graph G, we search for graphs G having the property that there is a pair of vertices u, v such that t(G; 1, –1) = t(G – {u, v}; 2, –1). Our main result gives a sufficient condition for a graph to have this property; moreover, it describes the graphs for which the property still holds when each vertex is replaced by a clique or a coclique of arbitrary order. In particular, we show that the property holds for the class of threshold graphs, a well-studied class of perfect graphs.     

Generalized Power Domination: Propagation Radius and Sierpiński Graphs

The recently introduced concept of k-power domination generalizes domination and power domination, the latter concept being used for monitoring an electric power system. The k-power domination problem is to determine a minimum size vertex subset S of a graph G such that after setting X=N[S], and iteratively adding to X vertices x that have a neighbour v in X such that at most k neighbours of v are not yet in X, we get X=V(G). In this paper the k-power domination number of Sierpiński graphs is determined. The propagation radius is introduced as a measure of the efficiency of power dominating sets. The propagation radius of Sierpiński graphs is obtained in most of the cases.     

On the maximal number of certain subgraphs inK r -free graphs

Given two graphsH andG, letH(G) denote the number of subgraphs ofG isomorphic toH. We prove that ifH is a bipartite graph with a one-factor, then for every triangle-free graphG withn verticesH(G) H(T ₂(n)), whereT ₂(n) denotes the complete bipartite graph ofn vertices whose colour classes are as equal as possible. We also prove that ifK is a completet-partite graph ofm vertices,r > t, n max(m, r – 1), then there exists a complete (r – 1)-partite graphG* withn vertices such thatK(G) K(G*) holds for everyK _r -free graphG withn vertices. In particular, in the class of allK _r -free graphs withn vertices the complete balanced (r – 1)-partite graphT _r–1(n) has the largest number of subgraphs isomorphic toK _t (t < r),C ₄,K _2,3. These generalize some theorems of Turán, Erdös and Sauer.Dedicated to Paul Turán on his 80th Birthday     

Anti‐periodic solutions for evolution equations with mappings in the class (S+)

In this paper, we study the existence of anti‐periodic solutions for the first order evolution equation in a Hilbert space H, where G : H → ? is an even function such that ?G is a mapping of class (S₊) and f : ? → ? satisfies f(t + T) = –f(t) for any t ∈ ? with f(·) ∈ L²(0, T; H). (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Isometric cycles,cutsets, and crowning of bridged graphs

A graph G is bridged if every cycle C of length at least 4 has vertices x,y such that d_G(x,y) < d_C(x,y). A cycle C is isometric if d_G(x,y) = d_C(x,y) for all x,y ∈ V(C). We show that every graph contractible to a graph with girth g has an isometric cycle of length at least g. We use this to show that every minimal cutset S in a bridged graph G induces a connected subgraph. We introduce a “crowning” construction to enlarge bridged graphs. We use this to construct examples showing that for every connected simple graph H with girth at least 6 (including trees), there exists a bridged graph G such that G has a unique minimum cutset S and that G[S] = H. This provides counterexamples to Hahn's conjecture that d_G(u,v) ≤ 2 when u and v lie in a minimum cutset in a bridged graph G. We also study the convexity of cutsets in bridged graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 161–170, 2003     

Graphs with unavoidable subgraphs with large degrees

Let ??(n, m) denote the class of simple graphs on n vertices and m edges and let G ∈ ?? (n, m). There are many results in graph theory giving conditions under which G contains certain types of subgraphs, such as cycles of given lengths, complete graphs, etc. For example, Turan's theorem gives a sufficient condition for G to contain a K_{k + 1} in terms of the number of edges in G. In this paper we prove that, for m = αn², α > (k - 1)/2k, G contains a K_{k + 1}, each vertex of which has degree at least f(α)n and determine the best possible f(α). For m = ?n²/4? + 1 we establish that G contains cycles whose vertices have certain minimum degrees. Further, for m = αn², α > 0 we establish that G contains a subgraph H with δ(H) ≥ f(α, n) and determine the best possible value of f(α, n).     

Odd‐angulated graphs and cancelling factors in box products

Under what conditions is it true that if there is a graph homomorphism G □ H → G □ T, then there is a graph homomorphism H→ T? Let G be a connected graph of odd girth 2k + 1. We say that G is (2k + 1)‐angulated if every two vertices of G are joined by a path each of whose edges lies on some (2k + 1)‐cycle. We call G strongly (2k + 1)‐angulated if every two vertices are connected by a sequence of (2k + 1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2k + 1)‐angulated, H is any graph, S, T are graphs with odd girth at least 2k + 1, and ?: G□ H→S□T is a graph homomorphism, then either ? maps G□{h} to S□{t_h} for all h∈V(H) where t_h∈V(T) depends on h; or ? maps G□{h} to {s_h}□ T for all h∈V(H) where s_h∈V(S) depends on h. This theorem allows us to prove several sufficient conditions for a cancelation law of a graph homomorphism between two box products with a common factor. We conclude the article with some open questions. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:221‐238, 2008     

A neighborhood condition which implies the existence of a class of d-chromatic subgraphs

A graph G of order n satisfies the neighborhood condition NC_k > s if any collection of k independent vertices is collectively adjacent to more than s vertices. Given a family H of graphs, the decomposition class β(H) is the family of graphs B with the property that for some H ∈ H of chromatic number d, H contains B as an induced subgraph and l?V(H) ? V(B)? is (d ? 2) colorable. Let H be a family of d-chromatic graphs, B an element of β(H) such that B contains an s-matching as an induced subgraph. Thus the cardinality of one of the partite sets of B is s + r for some integer r ≥ 0. We show that if t is a fixed positive integer, G is a graph of sufficiently large order n that satisfies the neighborhood condition then G contains B + K(d - 2; t) as a subgraph.     

On supercompact graphs

A graph G is called a supercompact graph if G is the intersection graph of some family ?? of subsets of a set X such that ?? satisfies the Helly property and for any x≠y in X, there exists S ∈ ?? with x ∈ S, y ? S. Various characterizations of supercompact graphs are given. It is shown that every clique-critical graph is supercompact. Furthermore, for any finite graph, H, there is at most a finite number of different supercompact graphs G such that H is the clique-graph of G.     

Two characterizations of chain partitioned probe graphs

Chain graphs are exactly bipartite graphs without induced 2K ₂ (a graph with four vertices and two disjoint edges). A graph G=(V,E) with a given independent set S⊆V (a set of pairwise non-adjacent vertices) is said to be a chain partitioned probe graph if G can be extended to a chain graph by adding edges between certain vertices in S. In this note we give two characterizations for chain partitioned probe graphs. The first one describes chain partitioned probe graphs by six forbidden subgraphs. The second one characterizes these graphs via a certain “enhanced graph”: G is a chain partitioned probe graph if and only if the enhanced graph G ^* is a chain graph. This is analogous to a result on interval (respectively, chordal, threshold, trivially perfect) partitioned probe graphs, and gives an O(m ²)-time recognition algorithm for chain partitioned probe graphs.     

K3,3-free intersection graphs of finite groups

The intersection graph of a group G is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper non-trivial subgroups of G, and there is an edge between two distinct vertices H and K if and only if H∩K≠1 where 1 denotes the trivial subgroup of G. In this paper we classify all finite groups whose intersection graphs are K_3,3-free.     

Iterated line graphs are maximally ordered

A graph G is k‐ordered if for every ordered sequence of k vertices, there is a cycle in G that encounters the vertices of the sequence in the given order. We prove that if G is a connected graph distinct from a path, then there is a number t_G such that for every t ≥ t_G the t‐iterated line graph of G, L^t (G), is (δ(L^t (G)) + 1)‐ordered. Since there is no graph H which is (δ(H)+2)‐ordered, the result is best possible. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 171–180, 2006     

Vertex-, edge-, and total-colorings of Sierpiński-like graphs

Vertex-colorings, edge-colorings and total-colorings of the Sierpiński gasket graphs S_n, the Sierpiński graphs S(n,k), graphs S⁺(n,k), and graphs S⁺⁺(n,k) are considered. In particular, χ^″(S_n), χ^′(S(n,k)), χ(S⁺(n,k)), χ(S⁺⁺(n,k)), χ^′(S⁺(n,k)), and χ^′(S⁺⁺(n,k)) are determined.     

Decompositions of complete graphs and complete bipartite graphs into isomorphic supersubdivision graphs

A graph H is called a supersubdivison of a graph G if H is obtained from G by replacing every edge uv of G by a complete bipartite graph K_2,m (m may vary for each edge) by identifying u and v with the two vertices in K_2,m that form one of the two partite sets. We denote the set of all such supersubdivision graphs by SS(G). Then, we prove the following results.

1. Each non-trivial connected graph G and each supersubdivision graph HSS(G) admits an α-valuation. Consequently, due to the results of Rosa (in: Theory of Graphs, International Symposium, Rome, July 1966, Gordon and Breach, New York, Dunod, Paris, 1967, p. 349) and El-Zanati and Vanden Eynden (J. Combin. Designs 4 (1996) 51), it follows that complete graphs K_2cq+1 and complete bipartite graphs K_mq,nq can be decomposed into edge disjoined copies of HSS(G), for all positive integers m,n and c, where q=|E(H)|.

2. Each connected graph G and each supersubdivision graph in SS(G) is strongly n-elegant, where n=|V(G)| and felicitous.

3. Each supersubdivision graph in EASS(G), the set of all even arbitrary supersubdivision graphs of any graph G, is cordial.

Further, we discuss a related open problem.     

Distinguishing Cartesian powers of graphs

The distinguishing number D(G) of a graph is the least integer d such that there is a d‐labeling of the vertices of G that is not preserved by any nontrivial automorphism of G. We show that the distinguishing number of the square and higher powers of a connected graph G ≠ K₂, K₃ with respect to the Cartesian product is 2. This result strengthens results of Albertson [Electron J Combin, 12 ( 1 ), #N17] on powers of prime graphs, and results of Klav?ar and Zhu [Eu J Combin, to appear]. More generally, we also prove that d(G □ H) = 2 if G and H are relatively prime and |H| ≤ |G| < 2^|H| ? |H|. Under additional conditions similar results hold for powers of graphs with respect to the strong and the direct product. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 250–260, 2006