共查询到20条相似文献,搜索用时 15 毫秒
1.
The energy of a simple graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Denote by Cn the cycle, and the unicyclic graph obtained by connecting a vertex of C6 with a leaf of Pn-6. Caporossi et al. conjectured that the unicyclic graph with maximal energy is for n=8,12,14 and n≥16. In Hou et al. (2002) [Y. Hou, I. Gutman, C. Woo, Unicyclic graphs with maximal energy, Linear Algebra Appl. 356 (2002) 27-36], the authors proved that is maximal within the class of the unicyclic bipartite n-vertex graphs differing from Cn. And they also claimed that the energies of Cn and is quasi-order incomparable and left this as an open problem. In this paper, by utilizing the Coulson integral formula and some knowledge of real analysis, especially by employing certain combinatorial techniques, we show that the energy of is greater than that of Cn for n=8,12,14 and n≥16, which completely solves this open problem and partially solves the above conjecture. 相似文献
2.
The energy of a simple graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let Cn denote the cycle of order n and the graph obtained from joining two cycles C6 by a path Pn-12 with its two leaves. Let Bn denote the class of all bipartite bicyclic graphs but not the graph Ra,b, which is obtained from joining two cycles Ca and Cb (a,b≥10 and ) by an edge. In [I. Gutman, D. Vidovi?, Quest for molecular graphs with maximal energy: a computer experiment, J. Chem. Inf. Sci. 41(2001) 1002-1005], Gutman and Vidovi? conjectured that the bicyclic graph with maximal energy is , for n=14 and n≥16. In [X. Li, J. Zhang, On bicyclic graphs with maximal energy, Linear Algebra Appl. 427(2007) 87-98], Li and Zhang showed that the conjecture is true for graphs in the class Bn. However, they could not determine which of the two graphs Ra,b and has the maximal value of energy. In [B. Furtula, S. Radenkovi?, I. Gutman, Bicyclic molecular graphs with the greatest energy, J. Serb. Chem. Soc. 73(4)(2008) 431-433], numerical computations up to a+b=50 were reported, supporting the conjecture. So, it is still necessary to have a mathematical proof to this conjecture. This paper is to show that the energy of is larger than that of Ra,b, which proves the conjecture for bipartite bicyclic graphs. For non-bipartite bicyclic graphs, the conjecture is still open. 相似文献
3.
Vincent Bouchitté 《Order》1985,2(2):119-122
We prove that a bipartite graph is chordal if and only if it has an elimination scheme. This leads to a polynomial algorithm to recognize whether an ordered set is cycle-free. 相似文献
4.
For a graph G, we define c(G) to be the minimal number of edges we must delete in order to make G into a covering graph of some poset. We prove that, if p=n
-1+(n)
,where (n) is bounded away from 0, then there is a constant k
0>0 such that, for a.e. G
p
, c(G
p
)k
0
n
1+(n)
.In other words, to make G
p
into a covering graph, we must almost surely delete a positive constant proportion of the edges. On the other hand, if p=n
-1+(n)
, where (n)0, thenc(G
p
)=o(n
1+(n)
), almost surely.Partially supported by MCS Grant 8104854. 相似文献
5.
Carsten Thomassen 《Order》1989,5(4):349-361
A plane Hasse representation of an acyclic oriented graph is a drawing of the graph in the Euclidean plane such that all arcs are straight-line segments directed upwards and such that no two arcs cross. We characterize completely those oriented graphs which have a plane Hasse representation such that all faces are bounded by convex polygons. From this we derive the Hasse representation analogue, due to Kelly and Rival of Fary's theorem on straight-line representations of planar graphs and the Kuratowski type theorem of Platt for acyclic oriented graphs with only one source and one sink. Finally, we describe completely those acyclic oriented graphs which have a vertex dominating all other vertices and which have no plane Hasse representation, a problem posed by Trotter. 相似文献
6.
Grzegorz Stachowiak 《Order》1988,5(3):257-259
The number of linear extensions among the orientations of a bipartite graph is maximum just if the orientation itself is bipartite, the natural one. 相似文献
7.
Debra D. Scott 《Order》1986,3(3):269-281
Competition graphs of transitive acyclic digraphs are strict upper bound graphs. This paper characterizes those posets, which can be considered transitive acyclic digraphs, which have upper bound graphs that are interval graphs. The results proved here may shed some light on the open question of those digraphs which have interval competition graphs.This material is taken from Chapter 3 of my (maiden name Diny) PhD Dissertation. 相似文献
8.
Pavel Holub 《Order》1985,2(3):321-322
Every graph G may be transformed into a covering graph either by deletion of edges or by subdivision. Let
E
(G) and
V
(G) denote corresponding minimal numbers. We prove
E
(G) =
V
(G) for every graph G. 相似文献
9.
Planar graphs and poset dimension 总被引:4,自引:0,他引:4
Walter Schnyder 《Order》1989,5(4):323-343
We view the incidence relation of a graph G=(V. E) as an order relation on its vertices and edges, i.e. a<G
b if and only of a is a vertex and b is an edge incident on a. This leads to the definition of the order-dimension of G as the minimum number of total orders on V E whose intersection is <G. Our main result is the characterization of planar graphs as the graphs whose order-dimension does not exceed three. Strong versions of several known properties of planar graphs are implied by this characterization. These properties include: each planar graph has arboricity at most three and each planar graph has a plane embedding whose edges are straight line segments. A nice feature of this embedding is that the coordinates of the vertices have a purely combinatorial meaning. 相似文献
10.
Two discrete modular lattice and have isomorphic graphs if and only if is of the form A × and is of the form A × for some lattices A and and . We prove that for discrete semimodular lattices and this latter condition holds if and only if and have isomorphic graphs and the isomorphism preserves the order on all cover-preserving sublattices of which are isomorphic to the seven-element, semimodular, nonmodular lattice (see Figure 1). This answers in the affirmative a question posed by J. Jakubik. 相似文献
11.
Alexander Kovačec 《Order》1989,6(3):245-263
Consider two partially ordered setsP, Q and a number of edges connecting some of the points ofP with some of the points ofQ. This yields a bipartite graph. Some pairs of the edges may cross each other because their endpoints atP andQ are oppositely ordered. A natural decrossing operation is to exchange the endpoints of these edges incident atQ, say. This is called a switch. A left lift of an edge means to replace its starting point atP by a larger starting point. A right lift is defined symmetrically for the endpoints atQ. The operation of adding an edge cannot, informally, be explained better. Assume we are given two bipartite graphs , on the node setPQ. We show that for certain pairs (P, Q) of finite posets, a neat necessary and sufficient criterion can be given in order that is obtainable from by the sequence of elementary operations just defined. A recent characterization of the Bruhat order of the symmetric group follows as a special case. 相似文献
12.
On reorienting graphs by pushing down maximal vertices 总被引:1,自引:0,他引:1
Oliver Pretzel 《Order》1986,3(2):135-153
We study the operation of pushing down elements in the diagram of a finite ordered set. Two natural questions about this operation are, ‘Which orientations of the underlying graph can be obtained from a given orientation by pushing down?’ and ‘Which sets of vertices can become the sets of maximal elements in such orientations?’. For both questions thére are easy necessary conditions. We show that these conditions are also sufficient. The results are extended to cover all induced subgraphs and arbitrary orientations of a finite graph. 相似文献
13.
Sanming Zhou 《Journal of Pure and Applied Algebra》2019,223(3):931-947
We study two families of cyclotomic graphs and perfect codes in them. They are Cayley graphs on the additive group of , with connection sets and , respectively, where () is an mth primitive root of unity, A a nonzero ideal of , and ? Euler's totient function. We call them the mth cyclotomic graph and the second kind mth cyclotomic graph, and denote them by and , respectively. We give a necessary and sufficient condition for to be a perfect t-code in and a necessary condition for to be such a code in , where is an integer and D an ideal of containing A. In the case when , is known as an Eisenstein–Jacobi and Gaussian networks, respectively, and we obtain necessary conditions for to be a perfect t-code in , where with β dividing α. In the literature such conditions are known to be sufficient when and under an additional condition. We give a classification of all first kind Frobenius circulants of valency 2p and prove that they are all pth cyclotomic graphs, where p is an odd prime. Such graphs belong to a large family of Cayley graphs that are efficient for routing and gossiping. 相似文献
14.
On graphs that can be oriented as diagrams of ordered sets 总被引:1,自引:0,他引:1
Oliver Pretzel 《Order》1985,2(1):25-40
We study some equivalent and necessary conditions for a finite graph to be the covering graph of a (partially) ordered set. For each 1, M. Aigner and G. Prins have introduced a notion of a vertex colouring, here called -good colouring, such that a 1-good colouring is the usual concept and graphs that have a 2-good colouring are precisely covering graphs. We present some inequalities for the corresponding chromatic numbers , especially for x
2. There exist graphs that satisfy these inequalities for =2 but are not covering graphs. We show also that x
2 cannot be bounded by a function of x=x
1. A construction of Neetil and Rödl is used to show that x
2 is not bounded by a function of the girth. 相似文献
15.
16.
Suppose G is a graph and λ1,λ2,…,λn are the eigenvalues of G. The Estrada index EE(G) of G is defined as the sum of eλi, 1≤i≤n. In this paper some new upper bounds for the Estrada index of bipartite graphs are presented. We apply our result on a (4,6)-fullerene to improve our bound given in an earlier paper. 相似文献
17.
LetG be a graph,VP(G) its vertex packing polytope and letA(G) be obtained by reflectingVP(G) in all Cartersian coordinates. Denoting byA*(G) the set obtained similarly from the fractional vertex packing polytope, we prove that the segment connecting any two non-antipodal
vertices ofA(G) is contained in the surface ofA(G) and thatG is perfect if and only ifA*(G) has a similar property. 相似文献
18.
John Greene 《Order》1990,6(4):351-366
If the level sets of a ranked partially ordered set are totally ordered, the greedy match between adjacent levels is defined by successively matching each vertex on one level to the first available unmatched vertex, if any, on the next level. Aigner showed that the greedy match produces symmetric chains in the Boolean algebra. We extend that result to partially ordered sets which are products of chains.It is widely thought that for Young's lattices corresponding to rectangles, the greedy match is complete. We show here that the greedy match is, in fact, complete for n×2, n×3 and n×4 rectangles but not for n×k rectangles if k5 and n is sufficiently large. 相似文献
19.
Aregression is a functiong from a partially ordered set to itself such thatg(x)≦x for allz. Amonotone k-chain is a chain ofk elementsx
1<x
2 <...<x
k
such thatg(x
1)≦g(x
2)≦...≦g(x
k
). If a partial order has sufficiently many elements compared to the size of its largest antichain, every regression on it
will have a monotone (k + 1)-chain. Fixingw, letf(w, k) be the smallest number such that every regression on every partial order with size leastf(w, k) but no antichain larger thanw has a monotone (k + 1)-chain. We show thatf(w, k)=(w+1)
k
.
Dedicated to Paul Erdős on his seventieth birthday
Research supported in part by the National Science Foundation under ISP-80-11451. 相似文献
20.
A theorem of N. Terai and T. Hibi for finite distributive lattices and a theorem of Hibi for finite modular lattices (suggested by R.P. Stanley) are equivalent to the following: if a finite distributive or modular lattice of rank d contains a complemented rank 3 interval, then the lattice is (d+1)-connected.In this paper, the following generalization is proved: Let L be a (finite or infinite) semimodular lattice of rank d that is not a chain (d∈N0). Then the comparability graph of L is (d+1)-connected if and only if L has no simplicial elements, where z∈L is simplicial if the elements comparable to z form a chain. 相似文献