摘要:

AbstractFor an integern⩾ 1, a graphGhas an n‐constant crossing numberif, for any two good drawings ϕ and ϕ′ ofGin the plane, μ(ϕ) ≡ μ(ϕ′) (modn), where μ(ϕ) is the number of crossings in ϕ. We prove that, except for trivial cases, a graphGhasn‐constant crossing number if and only ifn= 2 andGis eitherKporKq,r, wh

ISSN:0364-9024    

DOI:10.1002/jgt.3190120302

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1988

数据来源: WILEY

摘要:

AbstractTheinterval numberof a (simple, undirected) graphGis the least positive integertsuch thatGis the intersection graph of sets, each of which is the union oftreal intervals. Achordal(ortriangulated) graph is one with no induced cycles on 4 or more vertices. IfGis chordal and has maximum clique size ω(G) =m, theni(G) ⩽ [1 +o(1)]m/log2mand this result is best possible, even for split graphs (chordal graphs whose complement is also chorda

ISSN:0364-9024    

DOI:10.1002/jgt.3190120303

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1988

数据来源: WILEY

摘要:

AbstractLetH(n, i) be a simple (n− 1)‐pathv1→v2→ …︁ →vnwith an additional arcv1vi(3 ⩽i⩽n). We prove that for eachnandi(3 ⩽i⩽n), with few exceptions, everyn‐tournamentTnco

ISSN:0364-9024    

DOI:10.1002/jgt.3190120304

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1988

数据来源: WILEY

摘要:

AbstractA {1, 3, …,2n− 1}‐factor of a graphGis defined to be a spanning subgraph ofG, each degree of whose vertices is one of {1, 3, …, 2n− 1}, wherenis a positive integer. In this paper, we give a sufficient condition for a graph to have a {1, 3, …, 2n

ISSN:0364-9024    

DOI:10.1002/jgt.3190120305

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1988

数据来源: WILEY

摘要:

AbstractWe consider graphs drawn in the plane such that every edge crosses at most one other edge. We characterize, in terms of two forbidden sub‐configurations, which of these graphs are equivalent to drawings such that all edges are straight line segments. As a consequence we obtain a complete characterization of the pairs of dual graphs that can be represented as geometric dual graphs such that all edges except one are straight line segment

ISSN:0364-9024    

DOI:10.1002/jgt.3190120306

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1988

数据来源: WILEY

摘要:

AbstractIn this paper, we introduce a class of graphs that generalize threshold graphs by introducing threshold tolerances. Several characterizations of these graphs are presented, one of which leads to a polynomial‐time recognition algorithm. It is also shown that the complements of these graphs contain interval graphs and threshold graphs, and are contained in the subclass of chordal graphs called strongly chordal graphs, and in the class of interval tolerance graph

ISSN:0364-9024    

DOI:10.1002/jgt.3190120307

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1988

数据来源: WILEY

摘要:

AbstractIt is proved that every cubic graph with crossing number at least two contains a subdivision of one of eight graphs.

ISSN:0364-9024    

DOI:10.1002/jgt.3190120308

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1988

数据来源: WILEY

摘要:

AbstractThe average distance in a graph is defined as the average length of a shortest path between two vertices, taken over all pairs of vertices. This parameter can be contrasted with the diameter as a description of the metrical properties of the graph. If a vertex or edge is removed from a graph, in the worst case the average distance will increase. In this paper we consider the question, How small can the increase be if we choose the vertex or edge appropriately? If the graph is a cycle, the increase is roughly by a factor of 4/3. P. Winkler conjectured that any graph contains a vertex whose removal will not increase the average distance by more than a factor of 4/3. A similar conjecture can be made about removed edges, provided, for example, that the graph is 2‐edge‐connected. We prove the stronger statement that the edge version of the conjecture is true if the graph has no vertices of degree one. We also give an asymptotic affirmative answer for the vertex vers

ISSN:0364-9024    

DOI:10.1002/jgt.3190120309

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1988

数据来源: WILEY

摘要:

AbstractChvátal defined a graphGto be brittle if each induced subgraphFofGcontains a vertex that is not a midpoint of anyP4or not an endpoint of anyP4. Every brittle graph is perfectly orderable. In this paper, we prove that a graph is brittle whenever it is HHD‐free (containing no chordless cycle with at least five vertices, no cycle on six vertices with a long chord, and no complement of the chordless path on five vertices). We also design anO(n4) algorithm to recognize HHD‐free graphs, and also anO(n4) algorithm to construct a perfect order of an HHD‐free graph. It follows from this result that an optimal coloring and a largest clique of an HHD‐free graph can be found inO(

ISSN:0364-9024    

DOI:10.1002/jgt.3190120310

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1988

数据来源: WILEY

摘要:

AbstractLetGbe an undirected connected graph withnnodes. A subsetFof nodes ofGis a feedback vertex set (fvs) ifG−Fis a forest and a subsetJof nodes ofGis a nonseparating independent set (nsis) if no two nodes ofJare adjacent andG−Jis connected.f(G),z(G) denote the cardinalities of a minimum fvs and a maximum nsis, respectively, ofG.The equationf(G) =n/2 −z(G) + 1 and two new upper bounds onf(G) are derived for cubic gr

ISSN:0364-9024    

DOI:10.1002/jgt.3190120311

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1988

数据来源: WILEY