Spectral Characterization of Some Generalized Odd Graphs

Suppose G is a connected, k-regular graph such that Spec(G)=Spec(Γ) where Γ is a distance-regular graph of diameter d with parameters a ₁=a ₂=⋯=a _d−1=0 and a _d>0; i.e., a generalized odd graph, we show that G must be distance-regular with the same intersection array as that of Γ in terms of the notion of Hoffman Polynomials. Furthermore, G is isomorphic to Γ if Γ is one of the odd polygon C _2d+1, the Odd graph O _d+1, the folded (2d+1)-cube, the coset graph of binary Golay code (d=3), the Hoffman-Singleton graph (d=2), the Gewirtz graph (d=2), the Higman-Sims graph (d=2), or the second subconstituent of the Higman-Sims graph (d=2). Received: March 28, 1996 / Revised: October 20, 1997     

NOTE Spectral Characterization of Tree-Width-Two Graphs

) of a graph G, similar in spirit to his now-classical invariant . He showed that is minor-monotone and is related to the tree-width la(G) of G: and, moreover, , i.e. G is a forest. We show that and give the corresponding forbidden-minor and ear-decomposition characterizations. Received October 9, 1997/Revised July 27, 1999     

广义鸡尾酒宴图的谱特征

In the paper, we prove that all generalized cocktail-party graphs with order at least 23 are determined by their adjacency spectra.     

Strong Circuit Double Cover of Some Cubic Graphs

Let C be a given circuit of a bridgeless cubic graph G. It was conjectured by Seymour that G has a circuit double cover (CDC) containing the given circuit C. This conjecture (strong CDC [SCDC] conjecture) has been verified by Fleischner and Häggkvist for various families of graphs and circuits. In this article, some of these earlier results have been improved: (1) if contains a Hamilton path or a Y‐tree of order less than 14, then G has a CDC containing C; (2) if is connected and , then G has a CDC containing C.     

Spectral Characterizations of Some Distance-Regular Graphs

When can one see from the spectrum of a graph whether it is distance-regular or not? We give some new results for when this is the case. As a consequence we find (among others) that the following distance-regular graphs are uniquely determined by their spectrum: The collinearity graphs of the generalized octagons of order (2,1), (3,1) and (4,1), the Biggs-Smith graph, the M ₂₂ graph, and the coset graphs of the doubly truncated binary Golay code and the extended ternary Golay code.     

强正则图的一些性质

文[3]给出了强正则图的概念及有关性质,本文在此基地上利用图的谱性质,得到了强正则图的又一些性质。     

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.     

原始图与三次图的可圈度

本文综述关于原始图与三次图的可圈度的近期结果并提出一些未解决的问题。     

A Characterization of Cubic Graphs with Paired-Domination Number Three-Fifths Their Order

A paired-dominating set of a graph is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number is the minimum cardinality of a paired-dominating set in the graph. Recently, Chen et al. (Acta Math Sci Ser A Chin Ed 27(1):166–170, 2007) proved that a cubic graph has paired-domination number at most three-fifths the number of vertices in the graph. In this paper, we show that the Petersen graph is the only connected cubic graph with paired-domination number three-fifths its order.     

一类单圈图的拉普拉斯谱刻画

Let H（n; q, n1, n2, n3, n4） be a unicyclic graph with n vertices containing a cycle Cq and four hanging paths Ph1＋1, Pn2＋1, Pn3＋1 and Pn4＋1 attached at the same vertex of the cycle. In this paper, it is proved that all unicyclic graphs H （n; q, n1, n2, n3, n4） are determined by their Laplacian spectra.     

Amalgams of Cubic Bipartite Graphs

The amalgamation technique has been introduced for groups by Higman et al. [8] and Goldschmidt [7] and developed on geometries by Kegel and Schleiermacher [9]. We define a “graph amalgam” to point out a different approach to certain classes of cubic bipartite graphs. Furthermore, we find relations between graph amalgams, 3-bridges and star-products of cubic bipartite graphs.     

Antimagic Labeling of Cubic Graphs

An antimagic labeling of a graph G is a one‐to‐one correspondence between and such that the sum of the labels assigned to edges incident to distinct vertices are different. If G has an antimagic labeling, then we say G is antimagic. This article proves that cubic graphs are antimagic.     

Spectral Characterization of Odd Graphs Ok,k ≤6

Letk be an integer withk≥2. The Odd graphO _k has the(k- l)-subsets of 1,2,..., 2k-1 as vertices, and two vertices are adjacent if and only if their corresponding subsets are disjoint. We prove that the odd graphsO _k (k ≤ 6) are characterized by their spectra among connected regular graphs.     

关于三圈图的拉普拉斯谱半径的一些结果

边数等于点数加二的连通图称为三圈图.~设 ~$\Delta(G)$~和~$\mu(G)$~
分别表示图~$G$~的最大度和其拉普拉斯谱半径,设${\mathcal
T}(n)$~表示所有~$n$~阶三圈图的集合,证明了对于~${\mathcal
T}(n)$~的两个图~$H_{1}$~和~$H_{2}$~,~若~$\Delta(H_{1})>
\Delta(H_{2})$ ~且 ~$\Delta(H_{1})\geq \frac{n+7}{2}$,~则~$\mu
(H_{1})> \mu (H_{2}).$ 作为该结论的应用,~确定了~${\mathcal
T}(n)(n\geq9)$~中图的第七大至第十九大的拉普拉斯谱半径及其相应的极图.     

立方图的对控制数

设G=(V,E)是一个简单图, 对任意的顶点子集合 $S\subseteq V$, G[S]表示图G中由S所导出的子图. 如果S是G的一个控制集并且G[S]包含至少一个完备匹配, 则称S是G的一个对控制集. G中对控制集的最少的顶点数称为$G$的对控制数, 记为γ_p(G). 该文证明了对任意有n点的连通立方图G, γ_p(G)≤3n/ 5.     

Paired-Domination in Claw-Free Cubic Graphs

A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The minimum cardinality of a paired-dominating set of G is the paired-domination number of G, denoted by _pr(G). If G does not contain a graph F as an induced subgraph, then G is said to be F-free. In particular if F=K_1,3 or K₄–e, then we say that G is claw-free or diamond-free, respectively. Let G be a connected cubic graph of order n. We show that (i) if G is (K_1,3,K₄–e,C₄)-free, then _pr(G)3n/8; (ii) if G is claw-free and diamond-free, then _pr(G)2n/5; (iii) if G is claw-free, then _pr(G)n/2. In all three cases, the extremal graphs are characterized.Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal. This paper was written while the second author was visiting the Laboratoire de Recherche en Informatique (LRI) at the Université de Paris-Sud in July 2002. The second author thanks the LRI for their warm hospitality     

Independent Domination in Cubic Graphs

A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. The independent domination number of G, denoted by , is the minimum cardinality of an independent dominating set. In this article, we show that if is a connected cubic graph of order n that does not have a subgraph isomorphic to K_{2, 3}, then . As a consequence of our main result, we deduce Reed's important result [Combin Probab Comput 5 (1996), 277–295] that if G is a cubic graph of order n, then , where denotes the domination number of G.     

Cubic Bridgeless Graphs and Braces

There are many long-standing open problems on cubic bridgeless graphs, for instance, Jaeger’s directed cycle double cover conjecture. On the other hand, many structural properties of braces have been recently discovered. In this work, we bijectively map the cubic bridgeless graphs to braces which we call the hexagon graphs, and explore the structure of hexagon graphs. We show that hexagon graphs are braces that can be generated from the ladder on 8 vertices using two types of McCuaig’s augmentations. In addition, we present a reformulation of Jaeger’s directed cycle double cover conjecture in the class of hexagon graphs.