共查询到20条相似文献,搜索用时 15 毫秒
1.
A graph is a strict-quasi parity (SQP) graph if every induced subgraph that is not a clique contains a pair of vertices with
no odd chordless path between them (an “even pair”). We present an O(n
3) algorithm for recognizing planar strict quasi-parity graphs, based on Wen-Lian Hsu's decomposition of planar (perfect) graphs
and on the (non-algorithmic) characterization of planar minimal non-SQP graphs given in [9].
Received: September 21, 1998 Final version received: May 9, 2000 相似文献
2.
D.S. Franzblau 《Graphs and Combinatorics》2002,18(2):259-270
In this paper, a class of cubic planar graphs is given that have Hamiltonian cycles that can be constructed in linear time.
A member of this class is called a layered cubic planar graph, and consists of a sequence of cycles C
0
,C
1
,…,C
n
such that each pair of successive cycles, C
i
, C
i+1
, is joined by a matching. The cycles can be pictured as concentric circles, and the edges of the matchings as radial line
segments between successive circles. The subgraph bounded by two successive cycles forms a layer; each face in layer i is incident to a fixed number k
i+1
of edges in the matching in layer i+1. The problem that initially motivated this work is that of identifying classes of convex cubic polyhedra that can be easily
edge three-colored.
Received: September 21, 1998 Final version received: July 21, 1999 相似文献
3.
Yongwei Yao 《代数通讯》2013,41(11):4068-4077
In this article, we give an extension of the Fundamental Theorem of finite dimensional algebras to the case of ?2-graded algebras. Essentially, the results are the same as in the classical case, except that the notion of a ?2-graded division algebra needs to be modified. We classify all finite dimensional ?2-graded division algebras over ? and ?. 相似文献
4.
We prove that each 3-connected plane graph G without triangular or quadrangular faces either contains a k-path P
k
, a path on k vertices, such that each of its k vertices has degree ≤5/3k in G or does not contain any k-path. We also prove that each 3-connected pentagonal plane graph G which has a k-cycle, a cycle on k vertices, k∈ {5,8,11,14}, contains a k-cycle such that all its vertices have, in G, bounded degrees. Moreover, for all integers k and m, k≥ 3, k∉ {5,8,11,14} and m≥ 3, we present a graph in which every k-cycle contains a vertex of degree at least m.
Received: June 29, 1998 Final version received: April 11, 2000 相似文献
5.
Sheng Bau 《Graphs and Combinatorics》2002,18(2):201-208
A necessary and sufficient condition for the existence of a cycle containing a set of three vertices and an edge excluding
another edge is obtained for 3-connected cubic graphs by means of canonical contractions. A necessary and sufficient condition
is also obtained for a cyclically 4-connected cubic graph to have a cycle that contains a set of four vertices and that avoids
another vertex.
Received: October 4, 1999 Final version received: June 14, 2000 相似文献
6.
Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s
3(G) ≥ 2
k
−3, where s
r
(G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s
3(G) < 2
k
−2, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C
k
by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W
n
by deleting all but s consecutive spokes.
Received: January 29, 1999 Final version received: April 8, 2000 相似文献
7.
In this article we present characterizations of locally well-dominated graphs and locally independent well-dominated graphs,
and a sufficient condition for a graph to be k-locally independent well-dominated. Using these results we show that the irredundance number, the domination number and the
independent domination number can be computed in polynomial time within several classes of graphs, e.g., the class of locally
well-dominated graphs.
Received: September 13, 2001 Final version received: May 17, 2002
RID="*"
ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093)
RID="†"
ID="†" Supported by RUTCOR
RID="*"
ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093)
05C75, 05C69
Acknowledgments. The authors thank the referees for valuable suggestions. 相似文献
8.
Michael Capalbo 《Combinatorica》2002,22(3):345-359
For all positive integers N and k, let denote the family of planar graphs on N or fewer vertices, and with maximum degree k. For all positive integers N and k, we construct a -universal graph of size . This construction answers with an explicit construction the previously open question of the existence of such a graph.
Received July 8, 1998
RID="*"
ID="*" Supported by NSF grant CCR98210-58 and ARO grant DAAH04-96-1-0013. 相似文献
9.
Let G be a graph, and g, f, f′ be positive integer-valued functions defined on V(G). If an f′-factor of G is a spanning tree, we say that it is f′-tree. In this paper, it is shown that G contains a connected (g, f+f′−1)-factor if G has a (g, f)-factor and an f′-tree.
Received: October 30, 2000 Final version received: August 20, 2002 相似文献
10.
Let P
n
be a set of n=2m points that are the vertices of a convex polygon, and let ℳ
m
be the graph having as vertices all the perfect matchings in the point set P
n
whose edges are straight line segments and do not cross, and edges joining two perfect matchings M
1 and M
2 if M
2=M
1−(a,b)−(c,d)+(a,d)+(b,c) for some points a,b,c,d of P
n
. We prove the following results about ℳ
m
: its diameter is m−1; it is bipartite for every m; the connectivity is equal to m−1; it has no Hamilton path for m odd, m>3; and finally it has a Hamilton cycle for every m even, m≥4.
Received: October 10, 2000 Final version received: January 17, 2002
RID="*"
ID="*" Partially supported by Proyecto DGES-MEC-PB98-0933
Acknowledgments. We are grateful to the referees for comments that helped to improve the presentation of the paper. 相似文献
11.
We prove that for every c>0 there exists a constant K = K(c) such that every graph G with n vertices and minimum degree at least c
n contains a cycle of length t for every even t in the interval [4,e
c(G) − K] and every odd t in the interval [K,o
c(G) − K], where e
c(G) and o
c(G) denote the length of the longest even cycle in G and the longest odd cycle in G respectively. We also give a rough estimate of the magnitude of K.
Received: July 5, 2000 Final version received: April 17, 2002
2000 Mathematics Subject Classification. 05C38 相似文献
12.
Received: August 22, 1996 相似文献
13.
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. 相似文献
14.
Pil?niak and Wo?niak put forward the concept of neighbor sum distinguishing (NSD) total coloring and conjectured that any graph with maximum degree Δ admits an NSD total (Δ+3)-coloring in 2015. In 2016, Qu et al. showed that the list version of the conjecture holds for any planar graph with Δ ≥ 13. In this paper, we prove that any planar graph with Δ ≥ 7 but without 6-cycles satisfies the list version of the conjecture. 相似文献
15.
The bandwidth of a graph is the minimum, over vertex labelings with distinct integers, of the maximum difference between
labels on adjacent vertices. Kuang and McDiarmid proved that almost all n-vertex graphs have bandwidth . Thus the sum of the bandwidths of a graph and its complement is almost always at least ; we prove that it is always at most 2n−4 log 2
n+o(log n). The proofs involve improving the bounds on the Ramsey and Turán numbers of the “halfgraph”.
Received: September 2, 1998?Final version received: November 29, 1999 相似文献
16.
Janka Chlebíkov 《Discrete Applied Mathematics》2002,120(1-3):61-71
It is known that the class of graphs with treewidth (resp. pathwidth) bounded by a constant w can be characterized by a finite obstruction set obs(TW(w)) (resp. obs(PW(w))). These obstruction sets are known for w3 so far. In this paper we give a structural characterization of graphs from obs(TW(w)) (resp. obs(PW(w))) with a fixed number of vertices in terms of subgraphs of the complement. Our approach also essentially simplifies known characterization of graphs from obs(TW(w)) (resp. obs(PW(w))) with (w+3) vertices.
Also for any w3 a graph from obs(TW(w))obs(PW(w)) is constructed, that solves an open problem. 相似文献
17.
Andrew Lyons 《Discrete Applied Mathematics》2011,159(16):1842-1850
An acyclic coloring of a graph is a proper vertex coloring such that the union of any two color classes induces a disjoint collection of trees. The more restricted notion of star coloring requires that the union of any two color classes induces a disjoint collection of stars. We prove that every acyclic coloring of a cograph is also a star coloring and give a linear-time algorithm for finding an optimal acyclic and star coloring of a cograph. If the graph is given in the form of a cotree, the algorithm runs in O(n) time. We also show that the acyclic chromatic number, the star chromatic number, the treewidth plus 1, and the pathwidth plus 1 are all equal for cographs. 相似文献
18.
Given a graph G, a (k;a,b,c)-star in G is a subgraph isomorphic to a star K1,3 with a central vertex of degree k and three leaves of degrees a, b and c in G. The main result of the paper is:
Every planar graph G of minimum degree at least 3 contains a (k;a,b,c)-star with a≤ b≤ c and (i) k = 3, a≤ 10, or (ii) k = 4, a = 4, 4≤ b≤ 10, or (iii) k = 4, a = 5, 5≤ b≤ 9, or (iv) k = 4, 6≤ a≤ 7, 6≤ b≤ 8, or (v) k = 5, 4≤ a≤ 5, 5≤ b≤ 6 and 5≤ c≤ 7, or (vi) k = 5 and a = b = c = 6. 相似文献
19.
A non-empty set of vertices is called an even dominating set if each vertex in the graph is adjacent to an even number of vertices in the set (adjacency is reflexive). In this paper,
the Fibonacci polynomials are studied over GF(2) with particular emphasis on their divisibility properties and their relation to the existence of even dominating sets
in grid graphs and properties of a corresponding recurrence.
Received: March 15, 1999 Final version received: November 8, 1999 相似文献
20.
An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. A k-connected graph with no k-contractible edge is called contraction critically k-connected. For k≥4, we prove that if both G and its complement Gˉ are contraction critically k-connected, then |V(G)|<k
5/3+4k
3/2.
Received: October, 2001 Final version received: September 18, 2002
AMS Classification: 05C40 相似文献