On the degrees of a strongly vertex-magic graph

Let G=(V,E) be a finite graph, where |V|=n?2 and |E|=e?1. A vertex-magic total labeling is a bijection λ from V∪E to the set of consecutive integers {1,2,…,n+e} with the property that for every v∈V, for some constant h. Such a labeling is strong if λ(V)={1,2,…,n}. In this paper, we prove first that the minimum degree of a strongly vertex-magic graph is at least two. Next, we show that if , then the minimum degree of a strongly vertex-magic graph is at least three. Further, we obtain upper and lower bounds of any vertex degree in terms of n and e. As a consequence we show that a strongly vertex-magic graph is maximally edge-connected and hamiltonian if the number of edges is large enough. Finally, we prove that semi-regular bipartite graphs are not strongly vertex-magic graphs, and we provide strongly vertex-magic total labeling of certain families of circulant graphs.     

The edge-Wiener index of a graph

If G is a connected graph, then the distance between two edges is, by definition, the distance between the corresponding vertices of the line graph of G. The edge-Wiener index W_e of G is then equal to the sum of distances between all pairs of edges of G. We give bounds on W_e in terms of order and size. In particular we prove the asymptotically sharp upper bound for graphs of order n.     

On the Minimum Average Distance Spanning Tree of the Hypercube

Given an undirected and connected graph G, with a non-negative weight on each edge, the Minimum Average Distance (MAD) spanning tree problem is to find a spanning tree of G which minimizes the average distance between pairs of vertices. This network design problem is known to be NP-hard even when the edge-weights are equal. In this paper we make a step towards the proof of a conjecture stated by A.A. Dobrynin, R. Entringer and I. Gutman in 2001, and which says that the binomial tree B _n is a MAD spanning tree of the hypercube H _n . More precisely, we show that the binomial tree B _n is a local optimum with respect to the 1-move heuristic which, starting from a spanning tree T of the hypercube H _n , attempts to improve the average distance between pairs of vertices, by adding an edge e of H _n -T and removing an edge e′ from the unique cycle created by e. We also present a greedy algorithm which produces good solutions for the MAD spanning tree problem on regular graphs such as the hypercube and the torus.     

Consecutive magic graphs

Let G be a graph of order n and size e. A vertex-magic total labeling is an assignment of the integers 1,2,…,n+e to the vertices and the edges of G, so that at each vertex, the vertex label and the labels on the edges incident at that vertex, add to a fixed constant, called the magic number of G. Such a labeling is a-vertex consecutive magic if the set of the labels of the vertices is {a+1,a+2,…,a+n}, and is b-edge consecutive magic if the set of labels of the edges is {b+1,b+2,…,b+e}. In this paper we prove that if an a-vertex consecutive magic graph has isolated vertices then the order and the size satisfy (n-1)²+n²=(2e+1)². Moreover, we show that every tree with even order is not a-vertex consecutive magic and, if a tree of odd order is a-vertex consecutive then a=n-1. Furthermore, we show that every a-vertex consecutive magic graph has minimum degree at least two if a=0, or both and 2a?e, and the minimum degree is at least three if both and 2a?e. Finally, we state analogous results for b-edge consecutive magic graphs.     

On the distance spectral radius of cacti

A cactus is a connected graph in which any two cycles have at most one common vertex. In this article, we determine the unique graph with minimal distance spectral radius in the class of all cacti with n vertices and k cycles. Also, we determine the unique graph with minimal distance spectral radius in the class of all cacti with n vertices and r pendent vertices. Moreover, we determine the class of cacti in which the maximal distance spectral radius among all cacti with n vertices and k cycles is attained.     

On the reconstruction of the degree sequence

Harary's edge reconstruction conjecture states that a graph G=(V,E) with at least four edges is uniquely determined by the multiset of its edge-deleted subgraphs, i.e. the graphs of the form G−e for e∈E. It is well-known that this multiset uniquely determines the degree sequence of a graph with at least four edges. In this note we generalize this result by showing that the degree sequence of a graph with at least four edges is uniquely determined by the set of the degree sequences of its edge-deleted subgraphs with one well-described class of exceptions. Moreover, the multiset of the degree sequences of the edge-deleted subgraphs always allows one to reconstruct the degree sequence of the graph.     

On the Szeged and the Laplacian Szeged spectrum of a graph

For a given graph G its Szeged weighting is defined by w(e)=n_u(e)n_v(e), where e=uv is an edge of G,n_u(e) is the number of vertices of G closer to u than to v, and n_v(e) is defined analogously. The adjacency matrix of a graph weighted in this way is called its Szeged matrix. In this paper we determine the spectra of Szeged matrices and their Laplacians for several families of graphs. We also present sharp upper and lower bounds on the eigenvalues of Szeged matrices of graphs.     

Removable edges of cycles in 5-connected graphs

Let G be a 5-connected graph. For an edge e of G, we do the following operations on G: first, delete the edge e from G, resulting the graph G?e; second, for each vertex x of degree 4 in G?e, delete x from G?e and then completely connect the 4 neighbors of x by K ₄. If multiple edges occur, we use single edge to replace them. The final resultant graph is denoted by G ? e. If G ? e is still 5-connected, then e is called a removable edge of G. In this paper, we investigate the distribution of removable edges in a cycle of a 5-connected graph. And we give examples to show some of our results are best possible in some sense.     

On vertex symmetric digraphs

The problem of how “near” we can come to a n-coloring of a given graph is investigated. I.e., what is the minimum possible number of edges joining equicolored vertices if we color the vertices of a given graph with n colors. In its generality the problem of finding such an optimal color assignment to the vertices (given the graph and the number of colors) is NP-complete. For each graph G, however, colors can be assigned to the vertices in such a way that the number of offending edges is less than the total number of edges divided by the number of colors. Furthermore, an Ω(epn) deterministic algorithm for finding such an n-color assignment is exhibited where e is the number of edges and p is the number of vertices of the graph (e?p?n). A priori solutions for the minimal number of offending edges are given for complete graphs; similarly for equicolored K_m in K_p and equicolored graphs in K_p.     

A variation of a conjecture due to Erdös and Sós

Erdoes and Soes conjectured in 1963 that every graph G on n vertices with edge number e（G） 〉 1/2（k - 1）n contains every tree T with k edges as a subgraph. In this paper, we consider a variation of the above conjecture, that is, for n 〉 9/ 2k^2 ＋ 37/2＋ 14 and every graph G on n vertices with e（G） 〉 1/2 （k- 1）n, we prove that there exists a graph G＇ on n vertices having the same degree sequence as G and containing every tree T with k edges as a subgraph.     

On the distance spectral radius of some graphs

For a connected graph, the distance spectral radius is the largest eigenvalue of its distance matrix. In this paper, we determine the unique graph with minimum distance spectral radius among all connected graphs of order n with a given diameter. Moreover, we determine the unique graph with maximum distance spectral radius among the catacondensed hexagonal systems with h hexagons.     

Optimal graphs for chromatic polynomials

Let F(n,e) be the collection of all simple graphs with n vertices and e edges, and for G∈F(n,e) let P(G;λ) be the chromatic polynomial of G. A graph G∈F(n,e) is said to be optimal if another graph H∈F(n,e) does not exist with P(H;λ)?P(G;λ) for all λ, with strict inequality holding for some λ. In this paper we derive necessary conditions for bipartite graphs to be optimal, and show that, contrarily to the case of lower bounds, one can find values of n and e for which optimal graphs are not unique. We also derive necessary conditions for bipartite graphs to have the greatest number of cycles of length 4.     

Subdivisions of graphs: A generalization of paths and cycles

One of the basic results in graph theory is Dirac's theorem, that every graph of order n?3 and minimum degree ?n/2 is Hamiltonian. This may be restated as: if a graph of order n and minimum degree ?n/2 contains a cycle C then it contains a spanning cycle, which is just a spanning subdivision of C. We show that the same conclusion is true if instead of C, we choose any graph H such that every connected component of H is non-trivial and contains at most one cycle. The degree bound can be improved to (n-t)/2 if H has t components that are trees.We attempt a similar generalization of the Corrádi-Hajnal theorem that every graph of order ?3k and minimum degree ?2k contains k disjoint cycles. Again, this may be restated as: every graph of order ?3k and minimum degree ?2k contains a subdivision of kK₃. We show that if H is any graph of order n with k components, each of which is a cycle or a non-trivial tree, then every graph of order ?n and minimum degree ?n-k contains a subdivision of H.     

A bound on the total size of a cut cover

A cycle cover (cut cover) of a graph G is a collection of cycles (cuts) of G that covers every edge of G at least once. The total size of a cycle cover (cut cover) is the sum of the number of edges of the cycles (cuts) in the cover.We discuss several results for cycle covers and the corresponding results for cut covers. Our main result is that every connected graph on n vertices and e edges has a cut cover of total size at most 2e-n+1 with equality precisely when every block of the graph is an odd cycle or a complete graph (other than K₄ or K₈). This corresponds to the result of Fan [J. Combin. Theory Ser. B 74 (1998) 353-367] that every graph without cut-edges has a cycle cover of total size at most e+n-1.     

On infinite graphs with a specified number of colorings

In this paper we construct a planar graph of degree four which admits exactly N_u 3-colorings, we prove that such a graph must have degree at least four, and we consider various generalizations. We first allow our graph to have either one or two vertices of infinite degree and/or to admit only finitely many colorings and we note how this effects the degrees of the remaining vertices. We next consider n-colorings for n>3, and we construct graphs which we conjecture (but cannot prove) are of minimal degree. Finally, we consider nondenumerable graphs, and for every 3 <n<ω and every infinite cardinal k we construct a graph of cardinality k which admits exactly kn-colorings. We also show that the number of n-colorings of a denumerable graph can never be strictly between N_u and 2^N_u and that an appropriate generalization holds for at least certain nondenumerable graphs.     

Block transitivity and degree matrices: (Extended abstract)

We say that a square matrix M is a degree matrix of a given graph G if there is a so called equitable partition of its vertices into r blocks such that whenever two vertices belong to the same block, they have the same number of neighbors inside any block.We ask now whether for a given degree matrix M, there exists a graph G such that M is a degree matrix of G, and in addition, for any two edges e, f spanning between the same pair of blocks there exists an automorphism of G that sends e to f. In this work, we fully characterize the matrices for which such a graph exists and show a way to construct one.     

Three-Color Ramsey Numbers of K n Dropping an Edge

By an edge-coloring induced by generalization of Paley graph and computer searching, we show that that Ramsey numbers of K _n ? e in three colors for n =? 6, 7, 8, 9 are at least 472, 1102, 3208, 5962, respectively.     

Improvement on Brooks' chromatic bound for a class of graphs

Brooks' Theorem says that if for a graph G,Δ(G)=n, then G is n-colourable, unless (1) n=2 and G has an odd cycle as a component, or (2) n>2 and K_n+1 is a component of G. In this paper we prove that if a graph G has none of some three graphs (K_1,3;K₅?e and H) as an induced subgraph and if Δ(G)?6 and d(G)<Δ(G), then χ(G)<Δ(G). Also we give examples to show that the hypothesis Δ(G)?6 can not be non-trivially relaxed and the graph K₅?e can not be removed from the hypothesis. Moreover, for a graph G with none of K_1,3;K₅?e and H as an induced subgraph, we verify Borodin and Kostochka's conjecture that if for a graph G,Δ(G)?9 and d(G)<Δ(G), then χ(G)<Δ(G).