Super Edge-Magic Models

In this paper, we generalize the concept of super edge-magic graph by introducing the new concept of super edge-magic models.     

The Jumping Knight and Other (Super) Edge-Magic Constructions

Let G be a graph of order p and size q with loops allowed. A bijective function ${f:V(G)\cup E(G)\rightarrow \{i\}_{i=1}^{p+q}}$ is an edge-magic labeling of G if the sum ${f(u)+f(uv)+f(v)=k}$ is independent of the choice of the edge uv. The constant k is called either the valence, the magic weight or the magic sum of the labeling f. If a graph admits an edge-magic labeling, then it is called an edge-magic graph. Furthermore, if the function f meets the extra condition that ${f(V(G))=\{i\}_{i=1}^{p}}$ then f is called a super edge-magic labeling and G is called a super edge-magic graph. A digraph D admits a labeling, namely l, if its underlying graph, und(D) admits l. In this paper, we introduce a new construction of super edge-magic labelings which are related to the classical jump of the knight on the chess game. We also use super edge-magic labelings of digraphs together with a generalization of the Kronecker product to get edge-magic labelings of some families of graphs.     

On Super Restricted Edge Connectivity of Half Vertex Transitive Graphs

Let X =  (V, E) be a connected graph. Call X super restricted edge connected in short, sup-λ′, if F is a minimum edge set of X such that X − F is disconnected and every component of X − F has at least two vertices, then F is the set of edges adjacent to a certain edge with minimum edge degree in X. A bipartite graph is said to be half vertex transitive if its automorphism group is transitive on the sets of its bipartition. In this article, we show that every connected half vertex transitive graph X with n =  |V(X)| ≥  4 and X \ncong K_1,n-1{X \ncong K_{1,n-1}} is λ′-optimal. By studying the λ′-superatoms of X, we characterize sup-λ′ connected half vertex transitive graphs. As a corollary, sup-λ′ connected Bi-Cayley graphs are also characterized.     

图的超级限制边连通性

在Moor-Shannon网络模型中,边连通度和限制边连通度较大的网络一般有较好的可靠性和容错性.本文证明:除两种平凡情形外,无向Kautz网络的拓扑结构,无向Kautz图UK(2,n)是超级限制边连通的.因此,它们比de Bruijn网络有更好的限制边连通性.     

Super Restricted Edge Connectivity of Regular Graphs

An edge cut of a connected graph is called restricted if it separates this graph into components each having order at least 2; a graph G is super restricted edge connected if G−S contains an isolated edge for every minimum restricted edge cut S of G. It is proved in this paper that k-regular connected graph G is super restricted edge connected if k > |V(G)|/2+1. The lower bound on k is exemplified to be sharp to some extent. With this observation, we determined the number of edge cuts of size at most 2k−2 of these graphs. Supported by NNSF of China (10271105); Ministry of Science and Technology of Fujian (2003J036); Education Ministry of Fujian (JA03147)     

Super Connectivity of Line Graphs and Digraphs

The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ1（L） = 2λ1 （D）, and that for a connected graph G and its line graph L, if one of κ1 （L） and λ（G） exists, then κ1（L） = λ2（G）. This paper determines that κ1（B（d, n） is equal to 4d- 8 for n = 2 and d ≥ 4, and to 4d-4 for n ≥ 3 and d ≥ 3, and that κ1（K（d, n）） is equal to 4d- 4 for d 〉 2 and n ≥ 2 except K（2, 2）. It then follows that B（d,n） and K（d, n） are both super connected for any d ≥ 2 and n ≥ 1.     

Kronecker乘积图的超连通性(英文)

设G1和G2是两个连通图,则G1和G2的Kronecker积G1×G2定义如下:V(G1×G2)=V(G1)×V(G2),E(G1×G2)={(u1,v1)(u2,v2):u1u2∈E(G1),v1v2∈E(G2)}.我们证明了G×Kn(n≥4)超连通图当且仅当κ(G)n>δ(G)(n 1),其中G是任意的连通图,Kn是n阶完全图.进一步我们证明了对任意阶至少为3的连通图G,如果κ(G)=δ(G),则G×Kn(n≥3)超连通图.这个结果加强了郭利涛等人的结果.     

On the Decomposition of Graphs into Complete Bipartite Graphs

In a complete bipartite decomposition π of a graph, we consider the number ϑ(v;π) of complete bipartite subgraphs incident with a vertex v. Let ϑ(G)= ϑ(v;π). In this paper the exact values of ϑ(G) for complete graphs and hypercubes and a sharp upper bound on ϑ(G) for planar graphs are provided, respectively. An open problem proposed by P.C. Fishburn and P.L. Hammer is solved as well.     

On the Weak-Integrity of Graphs

Connectivity has been used in the past to describe the stability of graphs. If two graphs have the same connectivity, then it does not distinguish between these graphs. That is, the connectivity is not a good measure of graph stability. Then we need other graph parameters to describe the stability. Suppose that two graphs have the same connectivity and the order (the number of vertices or edges) of the largest components of these graphs are not equal. Hence, we say that these graphs must be different in respect to stability and so we can define a new measure which distinguishes these graphs. In this paper, the Weak-Integrity of a graph G is introduced as a new measure of stability in this sense and it is defined as I _w (G)=min _SV(G){S+m _e (G–S)}, where m _e (G–S) denotes the number of edges of the largest component of G–S. We give the weak-integrity of graphs obtained via various operations that are unary, such as powers, and binary, such as union, composition, product and corona.     

用超广义线图构造整谱图

线图在图的谱理论研究中起着重要的作用.在本文中,通过研究超广义线图成为整谱图的充分条件,获得了一种全新的构造新的整 谱图的方法,运用这种方法,可以构造出无穷多个新的整谱图.     

Super-edge-graceful Labelings of Some Cubic Graphs

The notion of super-edge-graceful graphs was introduced by Mitchem and Simoson in 1994.However, few examples except trees are known. In this paper, we exhibit two classes of infinitely many cubic graphs which are super-edge-graceful. A conjecture is proposed.     

门槛图与度极大图

证明了门槛图与度极大图是一类图的两种不同说法,同时用图的对角限制极左矩阵刻画这一类图的结构。     

On Compact Graphs

Let G be a finite simple graph with adjacency matrix A, and let P（A） be the convex closure of the set of all permutation matrices commuting with A. G is said to be compact if every doubly stochastic matrix which commutes with A is in P（A）. In this paper, we characterize 3-regular compact graphs and prove that if G is a connected regular compact graph, G - v is also compact, and give a family of almost regular compact connected graphs.     

On Factor-Uniform Graphs

Graphsunderconsiderationarefiniteundirected,andbasicgraph-theoreticnotationandtermsusedarethesamewiththatin[1].LetG=(V(G),E(G))beagraphwhichmayhaveloopsormultipleedges,Z~{0,if,12,.'.},g,f:V(G)-Z,p(g,f)~{xEV(G)lg(x)~f(x)}andp(g,f)GPgV(G).Supposeg(x)5f(x)forallxEV(G)andg(x)~f(x)(mod2)forallxEP.Thena(P,f)-congruent(g,f)-factorofGisaspanningsubgraphFofGsuchthatg(x)5dF(x)5f(x)forallxEV(G)anddF(x)~f(x)(mod2)forallxCP.Giscalled(g,f;p)-covered(-deleted,resp.)if,foreachedgeeofG,thereexist…     

On Azumaya Graphs

We study Azumaya multiplicative graphs over a suitable base category, generalizing in this way the theory of Azumaya algebras over a ring, with or without unit, and the theory of enriched Azumaya categories. We exhibit the links with the corresponding notions of centrality, separability, Brauer group and Brauer–Taylor group.     

On Interference Graphs

The study of interference graphs assumes significance in the context of the study of Frequency assignment problem. By an interference graph we mean the graph whose vertices represent a transmitter and the edges denote the interference constraint between two adjacent transmitters. In this paper we probe the relationship between 2-coloring and radio labeling and the effect of its computational aspect to certain restricted class of graphs. We also indicate some possible directions for further research.     

On Nearest-Neighbor Graphs

The ``nearest-neighbor' relation, or more generally the ``k-nearest-neighbors' relation, defined for a set of points in a metric space, has found many uses in computational geometry and clustering analysis, yet surprisingly little is known about some of its basic properties. In this paper we consider some natural questions that are motivated by geometric embedding problems. We derive bounds on the relationship between size and depth for the components of a nearest-neighbor graph and prove some probabilistic properties of the k-nearest-neighbors graph for a random set of points. Received March 31, 1995, and in revised form August 11, 1996.