On maximal circuits in directed graphs

An exact bound is obtained for the number of edges in a directed graph which ensures the existence of a circuit exceeding a prescribed length.Another proof of an analogous result of Erdös and Gallai for undirected graphs is supplied in the Appendix.     

阶数极大的临界全控制图

称一个没有孤立点的图G 为临界全控制图, 如果G 满足对于任何一个不与悬挂点相邻的顶点v, G - v 的全控制数都小于G 的全控制数. 如果G 的全控制数记为γ_t, 则称这样的临界全控制图G 为γ_t- 临界的. 如果G 是γ_t- 临界的, 且阶数为n, 则n ≤ Δ(G)(γ_t(G)- 1) + 1, 其中Δ(G) 是G 的最大度. 本文将证明对γ_t = 3, 这个阶数的上界是紧的, 并给出所有满足n = Δ(G)(γ_t(G)- 1) + 1 的3-γ_t- 临界图.     

On eigenfunctions and maximal cliques of generalised Paley graphs of square order

Let GP $(q^2,m)$ be the m-Paley graph defined on the finite field with order $q^2$. We study eigenfunctions and maximal cliques in generalised Paley graphs GP $(q^2,m)$, where $m|(q+1)$. In particular, we explicitly construct maximal cliques of size $\frac{q+1}{m}$ or $\frac{q+1}{m}+1$ in GP $(q^2,m)$, and show the weight-distribution bound on the cardinality of the support of an eigenfunction is tight for the smallest eigenvalue $-\frac{q+1}{m}$ of GP $(q^2,m)$. These new results extend the work of Baker et al. and Goryainov et al. on Paley graphs of square order. We also study the stability of the Erdős-Ko-Rado theorem for GP $(q^2,m)$ (first proved by Sziklai).     

On maximal triangle-free graphs

A triangle-free graph is maximal if adding any edge will create a triangle. The minimal number of edges of a maximal triangle-free graph on n vertices having maximal degree at most D is denoted by F(n, D). We determine the value of lim_n-∞ F(n, cn)/n for 2/5 < c < 1/2. This investigation continues work done by Z. Füredi and Á. Seress. Our result is contrary to a conjecture of theirs.     

On weighted directed graphs

The study of a mixed graph and its Laplacian matrix have gained quite a bit of interest among the researchers. Mixed graphs are very important for the study of graph theory as they provide a setup where one can have directed and undirected edges in the graph. In this article we present a more general structure, namely the weighted directed graphs and supply appropriate generalizations of several existing results for mixed graphs related to singularity of the corresponding Laplacian matrix. We also prove many new combinatorial results relating the Laplacian matrix and the graph structure.     

On antimagic directed graphs

An antimagic labeling of an undirected graph G with n vertices and m edges is a bijection from the set of edges of G to the integers {1, …, m} such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with that vertex. A graph is called antimagic if it admits an antimagic labeling. In (N. Hartsfield and G. Ringel, Pearls in Graph Theory, Academic Press, Boston, 1990, pp. 108–109), Hartsfield and Ringel conjectured that every simple connected graph, other than K₂, is antimagic. Despite considerable effort in recent years, this conjecture is still open. In this article we study a natural variation; namely, we consider antimagic labelings of directed graphs. In particular, we prove that every directed graph whose underlying undirected graph is “dense” is antimagic, and that almost every undirected d‐regular graph admits an orientation which is antimagic. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 219–232, 2010     

On the connectivity of maximal planar graphs

Let d₁ ? d₂ ? … ? d_p be the vertex degrees of a maximal planar graph G. Etourneau has shown that if d₁ ? 6 and d_p = 5, then G is 5-connected. We generalize Etourneau's result by giving sufficient conditions in terms of the vertex degrees for G to be d_p -connected.     

On reconstructing maximal outerplanar graphs

Manvel has proved that a maximal outerplanar graph can be reconstructed from the collection of isomorphism types of subgraphs obtained by deleting vertices of the given graph. This paper sharpens Manvel's result by showing that if the graph is not a triangulation of a hexagon, then reconstruction can be accomplished using only those isomorphism types of subgraphs corresponding to deletion of vertices of valence two.     

On the addressing problem for directed graphs

The “distance” from vertexu to vertexv in a strongly connected digraph is the number of arcs in a shortest directed path fromu tov. The addressing problem, first formulated in the undirected case by Graham and Pollak, entails the assignment of a string of symbols to each vertex in such a way that the distances between vertices are equal to modified Hamming distances between corresponding strings. A scheme for addressing digraphs is proposed, and the minimum address length is studied both in general and in certain special cases. The problem has some interesting reformulations in terms of matrix factorization and extremal set theory. Supported by NSF grant MCS 84-02054.     

Integral circulant graphs of prime power order with maximal energy

The energy of a graph is the sum of the moduli of the eigenvalues of its adjacency matrix. We study the energy of integral circulant graphs, also called gcd graphs, which can be characterized by their vertex count n and a set D of divisors of n in such a way that they have vertex set Z_n and edge set {{a,b}:a,b∈Z_n,gcd(a-b,n)∈D}. Using tools from convex optimization, we analyze the maximal energy among all integral circulant graphs of prime power order p^s and varying divisor sets D. Our main result states that this maximal energy approximately lies between s(p-1)p^s-1 and twice this value. We construct suitable divisor sets for which the energy lies in this interval. We also characterize hyperenergetic integral circulant graphs of prime power order and exhibit an interesting topological property of their divisor sets.     

On the maximal eccentric connectivity indices of graphs

For a connected simple graph G, the eccentricity ec(v) of a vertex v in G is the distance from v to a vertex farthest from v, and d(v) denotes the degree of a vertex v. The eccentric connectivity index of G, denoted by ξc(G), is defined as v∈V(G)d(v)ec(v). In this paper, we will determine the graphs with maximal eccentric connectivity index among the connected graphs with n vertices and m edges(n ≤ m ≤ n + 4), and propose a conjecture on the graphs with maximal eccentric connectivity index among the connected graphs with n vertices and m edges(m ≥ n + 5).     

On bicyclic graphs with maximal energy

Let λ₁,λ₂,…,λ_n be the eigenvalues of a graph G of order n. The energy of G is defined as E(G)=|λ₁|+|λ₂|+?+|λ_n|. Let be the graph obtained from two copies of C₆ joined by a path P_n-10, B_n be the class of all bipartite bicyclic graphs that are not the graph obtained from two cycles C_a and C_b (a,b?10 and a≡b≡2 (mod 4)) joined by an edge. In this paper, we show that is the graph with maximal energy in B_n, which gives a partial solution to Gutman’s conjecture in Gutman and Vidovi? (2001) [I. Gutman, D. Vidovi?, Quest for molecular graphs with maximal energy: a computer experiment, J. Chem. Inf. Sci. 41 (2001) 1002-1005].     

On the Markov equivalence of maximal ancestral graphs

Necessary and sufficient conditions for a maximal ancestral graph (MAnG) to be Markov equivalent to another MAnG and to a DAG are provided respectively. Also a polynomial-time algorithm for converting a MAnG into its equivalent DAG is given for the first time.     

On the tightness conditions for maximal planar graphs

We characterize the tight structure of a vertex-accumulation-free maximal planar graph with no separating triangles. Together with the result of Halin who gave an equivalent form for such graphs, this yields that a tight structure always exists in every 4-connected maximal planar graph with one end.     

On directed zero-divisor graphs of finite rings

For an artinian ring R, the directed zero-divisor graph Γ(R) is connected if and only if there is no proper one-sided identity element in R. Sinks and sources are characterized and clarified for a finite ring R. Especially, it is proved that for any ring R, if there exists a source y in Γ(R) with y²=0, then |R|=4 and R={0,x,y,z}, where x and z are left identity elements and yx=0=yz. Such a ring R is also the only ring such that Γ(R) has exactly one source. This shows that Γ(R) cannot be a network for any finite or infinite ring R.