Further characterizations of cubic lattice graphs

A cubic lattice graph with characteristic n is a graph whose points can be identified with the ordered triplets on n symbols and two points are adjacent whenever the corresponding triplets have two coordinates in common. An L₂ graph is a graph whose points can be identified with the ordered pairs on n symbols such that two points are adjacent if and only if the corresponding pairs have a common coordinate. The main result of this paper is two new characterizations and shows the relation between cubic lattice and L₂ graphs. The main result also suggests a conjecture concerning the characterization of interchange graphs of complete m-partite graphs.     

Note on group distance magic complete bipartite graphs

A Γ-distance magic labeling of a graph G = (V, E) with |V| = n is a bijection ? from V to an Abelian group Γ of order n such that the weight $w(x) = \sum\nolimits_{y \in N_G (x)} {\ell (y)}$ of every vertex x ∈ V is equal to the same element µ ∈ Γ, called the magic constant. A graph G is called a group distance magic graph if there exists a Γ-distance magic labeling for every Abelian group Γ of order |V(G)|. In this paper we give necessary and sufficient conditions for complete k-partite graphs of odd order p to be ? _p -distance magic. Moreover we show that if p ≡ 2 (mod 4) and k is even, then there does not exist a group Γ of order p such that there exists a Γ-distance labeling for a k-partite complete graph of order p. We also prove that K _m,n is a group distance magic graph if and only if n + m ? 2 (mod 4).     

Graham’s pebbling conjecture on product of thorn graphs of complete graphs

The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of pebbling moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Let p₁,p₂,…,p_n be positive integers and G be such a graph, V(G)=n. The thorn graph of the graph G, with parameters p₁,p₂,…,p_n, is obtained by attaching p_i new vertices of degree 1 to the vertex u_i of the graph G, i=1,2,…,n. Graham conjectured that for any connected graphs G and H, f(G×H)≤f(G)f(H). We show that Graham’s conjecture holds true for a thorn graph of the complete graph with every by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are the thorn graphs of the complete graphs with every .     

A characterization of complete matroid base graphs

This study grew from an attempt to give a local analysis of matroid base graphs. A neighborhood-preserving covering of graphs p:G → H is one such that p restricted to every neighborhood in G is an isomorphism. This concept arises naturally when considering graphs with a prescribed set of local properties. A characterization is given of all connected graphs with two local properties: (a) there is a pair of adjacent points, the intersection of whose neighborhoods does not contain three mutually nonadjacent points; (b) the intersection of the neigh-borhoods of points two apart is a 4-cycle. Such graphs have neighborhoods of the form K_n × K_m for fixed n, m and are either complete matroid base graphs or are their images under neighborhood-preserving coverings. If n ≠ m, the graph is unique; if n = m, there are n ? 3 such images which are nontrivial. These examples prove that no set of properties of bounded diameter can characterize matroid base graphs.     

Clique graphs of time graphs

A simple, finite graph G is called a time graph (equivalently, an indifference graph) if there is an injective real function f on the vertices v(G) such that v_iv_j ∈ e(G) for v_i ≠ v_j if and only if |f(v_i) ? f(v_j)| ≤ 1. A clique of a graph G is a maximal complete subgraph of G. The clique graph K(G) of a graph G is the intersection graph of the cliques of G. It will be shown that the clique graph of a time graph is a time graph, and that every time graph is the clique graph of some time graph. Denote the clique graph of a clique graph of G by K²(G), and inductively, denote K(K^m?1(G)) by K^m(G). Define the index indx(G) of a connected time graph G as the smallest integer n such that Kⁿ(G) is the trivial graph. It will be shown that the index of a time graph is equal to its diameter. Finally, bounds on the diameter of a time graph will be derived.     

Chromatic equivalence classes of complete tripartite graphs

Some necessary conditions on a graph which has the same chromatic polynomial as the complete tripartite graph K_m,n,r are developed. Using these, we obtain the chromatic equivalence classes for K_m,n,n (where 1≤m≤n) and K_m1,m2,m3 (where |m_i−m_j|≤3). In particular, it is shown that (i) K_m,n,n (where 2≤m≤n) and (ii) K_m1,m2,m3 (where |m_i−m_j|≤3, 2≤m_i,i=1,2,3) are uniquely determined by their chromatic polynomials. The result (i), proved earlier by Liu et al. [R.Y. Liu, H.X. Zhao, C.Y. Ye, A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs, Discrete Math. 289 (2004) 175-179], answers a conjecture (raised in [G.L. Chia, B.H. Goh, K.M. Koh, The chromaticity of some families of complete tripartite graphs (In Honour of Prof. Roberto W. Frucht), Sci. Ser. A (1988) 27-37 (special issue)]) in the affirmative, while result (ii) extends a result of Zou [H.W. Zou, On the chromatic uniqueness of complete tripartite graphs K_n1,n2,n3 J. Systems Sci. Math. Sci. 20 (2000) 181-186].     

On Harary index of graphs

The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. For a connected graph G=(V,E) and two nonadjacent vertices v_i and v_j in V(G) of G, recall that G+v_iv_j is the supergraph formed from G by adding an edge between vertices v_i and v_j. Denote the Harary index of G and G+v_iv_j by H(G) and H(G+v_iv_j), respectively. We obtain lower and upper bounds on H(G+v_iv_j)−H(G), and characterize the equality cases in those bounds. Finally, in this paper, we present some lower and upper bounds on the Harary index of graphs with different parameters, such as clique number and chromatic number, and characterize the extremal graphs at which the lower or upper bounds on the Harary index are attained.     

Uniformly optimal graphs in some classes of graphs with node failures

The uniformly optimal graph problem with node failures consists of finding the most reliable graph in the class Ω(n,m) of all graphs with n nodes and m edges in which nodes fail independently and edges never fail. The graph G is called uniformly optimal in Ω(n,m) if, for all node-failure probabilities q∈(0,1), the graph G is the most reliable graph in the class of graphs Ω(n,m). This paper proves that the multipartite graphs K(b,b+1,…,b+1,b+2) are uniformly optimal in their classes Ω((k+2)(b+1),(k²+3k+2)(b+1)²/2−1), where k is the number of partite sets of size (b+1), while for i>2, the multipartite graphs K(b,b+1,…,b+1,b+i) are not uniformly optimal in their classes Ω((k+2)b+k+i,(k+2)(k+1)b²/2+(k+1)(k+i)b+k(k+2i−1)/2).     

Critically indecomposable graphs

An undirected graph G=(V,E) with a specific subset X⊂V is called X-critical if G and G(X), induced subgraph on X, are indecomposable but G(V−{w}) is decomposable for every w∈V−X. This is a generalization of critically indecomposable graphs studied by Schmerl and Trotter [J.H. Schmerl, W.T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Mathematics 113 (1993) 191-205] and Bonizzoni [P. Bonizzoni, Primitive 2-structures with the (n−2)-property, Theoretical Computer Science 132 (1994) 151-178], who deal with the case where X is empty.We present several structural results for this class of graphs and show that in every X-critical graph the vertices of V−X can be partitioned into pairs (a₁,b₁),(a₂,b₂),…,(a_m,b_m) such that G(V−{a_j1,b_j1,…,a_jk,b_jk}) is also an X-critical graph for arbitrary set of indices {j₁,…,j_k}. These vertex pairs are called commutative elimination sequence. If G is an arbitrary indecomposable graph with an indecomposable induced subgraph G(X), then the above result establishes the existence of an indecomposability preserving sequence of vertex pairs (x₁,y₁),…,(x_t,y_t) such that x_i,y_i∈V−X. As an application of the commutative elimination sequence of an X-critical graph we present algorithms to extend a 3-coloring (similarly, 1-factor) of G(X) to entire G.     

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₂.     

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.     

Cliques, minors and apex graphs

In this paper, we proved the following result: Let G be a (k+2)-connected, non-(k−3)-apex graph where k≥2. If G contains three k-cliques, say L₁, L₂, L₃, such that |L_i∩L_j|≤k−2(1≤i<j≤3), then G contains a K_k+2 as a minor. Note that a graph G is t-apex if G−X is planar for some subset X⊆V(G) of order at most t.This theorem generalizes some earlier results by Robertson, Seymour and Thomas [N. Robertson, P.D. Seymour, R. Thomas, Hadwiger conjecture for K₆-free graphs, Combinatorica 13 (1993) 279-361.], Kawarabayashi and Toft [K. Kawarabayashi, B. Toft, Any 7-chromatic graph has K₇ or K_4,4 as a minor, Combinatorica 25 (2005) 327-353] and Kawarabayashi, Luo, Niu and Zhang [K. Kawarabayashi, R. Luo, J. Niu, C.-Q. Zhang, On structure of k-connected graphs without K_k-minor, Europ. J. Combinatorics 26 (2005) 293-308].     

The inertia set of the join of graphs

Let G=(V,E) be a graph with V={1,2,…,n}. Denote by S(G) the set of all real symmetric n×n matrices A=[a_i,j] with a_i,j≠0, i≠j if and only if ij is an edge of G. Denote by I^↗(G) the set of all pairs (p,q) of natural numbers such that there exists a matrix A∈S(G) with at most p positive and q negative eigenvalues. We show that if G is the join of G₁ and G₂, then I^↗(G)?{(1,1)}=I^↗(G₁∨K₁)∩I^↗(G₂∨K₁)?{(1,1)}. Further, we show that if G is a graph with s isolated vertices, then , where denotes the graph obtained from G be removing all isolated vertices, and we give a combinatorial characterization of graphs G with (1,1)∈I^↗(G). We use these results to determine I^↗(G) for every complete multipartite graph G.     

Bandwidth of the corona of two graphs

The bandwidth B(G) of a graph G is the minimum of the quantity max{|f(u)-f(v)|:uv∈E(G)} taken over all injective integer numberings f of G. The corona of two graphs G and H, written as G°H, is the graph obtained by taking one copy of G and |V(G)| copies of H, and then joining the ith vertex of G to every vertex in the ith copy of H. In this paper, we investigate the bandwidth of the corona of two graphs. For a graph G, we denote the connectivity of G by κ(G). Let G be a graph on n vertices with B(G)=κ(G)=k?2 and let H be a graph of order m. Let c,p and q be three integers satisfying 1?c?k-1 and . We define h_i=(2k-1)m+(k-i)(⌊(2k-1)m/i⌋+1)+1 for i=1,2,…,k and b=max{⌈(n(m+1)-qm-1)/(p+2)⌉,⌈(n(m+1)+k-q-1)/(p+3)⌉}. Then, among other results, we prove that

     

On bipartite zero-divisor graphs

A (finite or infinite) complete bipartite graph together with some end vertices all adjacent to a common vertex is called a complete bipartite graph with a horn. For any bipartite graph G, we show that G is the graph of a commutative semigroup with 0 if and only if it is one of the following graphs: star graph, two-star graph, complete bipartite graph, complete bipartite graph with a horn. We also prove that a zero-divisor graph is bipartite if and only if it contains no triangles. In addition, we give all corresponding zero-divisor semigroups of a class of complete bipartite graphs with a horn and determine which complete r-partite graphs with a horn have a corresponding semigroup for r≥3.     

Bandwidth theorem for random graphs

A graph G is said to have bandwidth at most b, if there exists a labeling of the vertices by 1,2,…,n, so that |i−j|?b whenever {i,j} is an edge of G. Recently, Böttcher, Schacht, and Taraz verified a conjecture of Bollobás and Komlós which says that for every positive r, Δ, γ, there exists β such that if H is an n-vertex r-chromatic graph with maximum degree at most Δ which has bandwidth at most βn, then any graph G on n vertices with minimum degree at least (1−1/r+γ)n contains a copy of H for large enough n. In this paper, we extend this theorem to dense random graphs. For bipartite H, this answers an open question of Böttcher, Kohayakawa, and Taraz. It appears that for non-bipartite H the direct extension is not possible, and one needs in addition that some vertices of H have independent neighborhoods. We also obtain an asymptotically tight bound for the maximum number of vertex disjoint copies of a fixed r-chromatic graph H₀ which one can find in a spanning subgraph of G(n,p) with minimum degree (1−1/r+γ)np.     

Comparing Zagreb indices for connected graphs

It was conjectured that for each simple graph G=(V,E) with n=|V(G)| vertices and m=|E(G)| edges, it holds M₂(G)/m≥M₁(G)/n, where M₁ and M₂ are the first and second Zagreb indices. Hansen and Vuki?evi? proved that it is true for all chemical graphs and does not hold in general. Also the conjecture was proved for all trees, unicyclic graphs, and all bicyclic graphs except one class. In this paper, we show that for every positive integer k, there exists a connected graph such that m−n=k and the conjecture does not hold. Moreover, by introducing some transformations, we show that M₂/(m−1)>M₁/n for all bicyclic graphs and it does not hold for general graphs. Using these transformations we give new and shorter proofs of some known results.     

Graphs omitting sums of complete graphs

For every finite m and n there is a finite set {G₁, …, G_l} of countable (m · K_n)-free graphs such that every countable (m · K_n)-free graph occurs as an induced subgraph of one of the graphs G_l © 1997 John Wiley & Sons, Inc.     

Properties of connected graphs having minimum degree distance

The degree distance of a connected graph, introduced by Dobrynin, Kochetova and Gutman, has been studied in mathematical chemistry. In this paper some properties of graphs having minimum degree distance in the class of connected graphs of order n and size m≥n−1 are deduced. It is shown that any such graph G has no induced subgraph isomorphic to P₄, contains a vertex z of degree n−1 such that G−z has at most one connected component C such that |C|≥2 and C has properties similar to those of G.For any fixed k such that k=0,1 or k≥3, if m=n+k and n≥k+3 then the extremal graph is unique and it is isomorphic to K₁+(K_1,k+1∪(n−k−3)K₁).