An Excluded-Minor Problem in Matroids

Consider the class of matroids M with the property that M is not isomorphic to a wheel graph, but has an element e such that both M\e and M/e are isomorphic to a series-parallel extension of a wheel graph. We give a constructive characterization of such matroids by determining explicitly the 3-connected members of the class. We also relate this problem with excluded minor problems.Received May 30, 2003     

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     

Spectral Characterization of Some Cubic Graphs

It is proved that the Cartesian product of an odd cycle with the complete graph on 2 vertices, is determined by the spectrum of the adjacency matrix. We also present some computational results on the spectral characterization of cubic graphs on at most 20 vertices.     

A Characterization of Domination Reducible Graphs

We introduce a hereditary class of domination reducible graphs where the minimum dominating set problem is polynomially solvable, and characterize this class in terms of forbidden induced subgraphs.Acknowledgments The research was supported by DIMACS 2002 and 2003 Awards. The author would like to thank the both referees for their valuable suggestions.Final version received: October 3, 2003     

A Characterization of Mixed Unit Interval Graphs

We give a complete characterization of mixed unit interval graphs, the intersection graphs of closed, open, and half‐open unit intervals of the real line. This is a proper superclass of the well‐known unit interval graphs. Our result solves a problem posed by Dourado, Le, Protti, Rautenbach, and Szwarcfiter (Mixed unit interval graphs, Discrete Math 312, 3357–3363 (2012)).     

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     

A Characterization of Graphs without Even Factors

In this paper, we first reduce the problem of finding a minimum parity (g,f)-factor of a graph G into the problem of finding a minimum perfect matching in a weighted simple graph G*. Using the structure of G*, a necessary and sufficient condition for the existence of an even factor is derived. This paper was accomplished while the second author was visiting the Center for Combinatorics, Nankai University. The research is supported by NSFC     

Characterization of Product Anti-Magic Graphs of Large Order

A graph G is product anti-magic if one can bijectively label its edges with integers 1, . . . ,e(G) so that no two vertices have the same product of incident labels. This property was introduced by Figueroa-Centeno, Ichishima, and Muntaner-Batle who in particular conjectured that every connected graph with at least 4 vertices is product anti-magic. Here, we completely describe all product anti-magic graphs of sufficiently large order, confirming the above conjecture in this case. Our proof uses probabilistic methods. Reverts to public domain 28 years from publication. Partially supported by the National Science Foundation, Grant DMS-0457512.     

Disjoint Paths in Graphs III,Characterization

Let G be a graph, $ \{a, b, c\}\subseteq V(G) $, and $ \{a', b', c'\}\subseteq V(G) $ such that $ \{a, b, c\}\neq \{a', b', c'\} $. We say that $ (G, \{a, c\}, \{a', c'\}, (b, b')) $ is an obstruction if, for any three vertex disjoint paths from {a, b, c} to {a', b', c'} in G, one path is from b to b'. In this paper we characterize obstructions. As a consequence, we show that no obstruction can be 8-connected, unless b = b' or {a, c} = {a', c'}.AMS Subject Classification: 05C38.     

A Characterization of Graphs with No Cube Minor

In this paper it is shown that any 4-connected graph that does not contain a minor isomorphic to the cube is a minor of the line graph of V_n for some n6 or a minor of one of five graphs. Moreover, there exists a unique 5-connected graph on at least 8 vertices with no cube minor and a unique 4-connected graph with a vertex of degree at least 8 with no cube minor. Further, it is shown that any graph with no cube minor is obtained from 4-connected such graphs by 0-, 1-, and 2-summing, and 3-summing over a specified triangles.     

A Characterization of Distance-Regular Graphs with Diameter Three

We characterize the distance-regular graphs with diameter three by giving an expression for the number of vertices at distance two from each given vertex, in terms of the spectrum of the graph.     

A Characterization of the Hamming Graphs and the Dual Polar Graphs by Completely Regular Subgraphs

In this paper we study a distance-regular graph Γ of diameter d ≥? 3 which satisfies the following two conditions: (a) For any integer i with 1 ≤? i ≤? d ? 1 and for any pair of vertices at distance i in Γ there exists a strongly closed subgraph of diameter i containing them; (b) There exists a strongly closed subgraph Δ which is completely regular in Γ. It is known that if Δ has diameter 1, then Γ is a regular near polygon. We prove that if a strongly closed subgraph Δ of diameter j with 2 ≤? j ≤? d ? 1 is completely regular of covering radius d ? j in Γ, then Γ is either a Hamming graph or a dual polar graph.     

匹配数与控制数相等的图的结构性质

我们分别用γ(G)，β(G)和α(G)表示图G的控制数、匹配数和覆盖数，对任意连通图，有γ(G)≤β(G)≤α(G)成立，1998年，Randerath和Volkmann给出了控制数等于覆盖数的图的特征，本文首先证明了匹配数与控制数相等的图其最小度不超过2，而后给出了最小度为2的图的结构性质。     

An Extremal Characterization of the Incidence Graphs of Projective Planes

Let G be a 4-cycle free, bipartite graph on 2n vertices with partitions of equal cardinality n. Let c₆(G) denote the number of cycles of length 6 in G. We prove that for n 3, c₆(G) , where , with equality if and only if G is the incidence point-line graph of a projective plane.     

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.     

A Characterization of the Optimal p-sum Labellingsof Unit Interval Graphs

1.IntroductionGraphsconsideredinthispaperarefiniteandsimple.FOragraphG,V(G)andE(G)denoteitssetofvenicesandedges,respectively.AbijectionwillbecalledalabellingofG.Letpbeapositiverealnumber.ForagivenlabellingTofagraphG,definethegndiscrepencya.(G,ac)ofTasTheobjectiveoftheminimum-p--sumproblemistofindalabelling7ofagraphGsuchthatac(G,T)isassmallaspossible.ThelabellingTminimizinga.(G,7)iscalledanoptimalHsumlabellingofG.Theminimumvalueiscalledtheminimum-psumofG.ItisshowninI31thattheminimum-…