摘要:

AbstractIn this paper we discuss a generalization of the familiar concept of an interval graph that arises naturally in scheduling and allocation problems. We define the interval number of a graphGto be the smallest positive integertfor which there exists a functionfwhich assigns to each vertexuofGa subsetf(u) of the real line so thatf(u) is the union oftclosed intervals of the real line, and distinct verticesuandvinGare adjacent if and only iff(u) andf(v)meet. We show that (1) the interval number of a tree is at most two, and (2) the complete bipartite graphKm, nhas interval number ⌈(mn+ 1)/(m+n)

ISSN:0364-9024    

DOI:10.1002/jgt.3190030302

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

年代:1979

数据来源: WILEY

摘要:

AbstractIt is shown that storng blocks, i.e., digraphs that are strongly connected and have no cutnodes have an ear‐decomposition. This result is used to prove that the numberqof arcs of minimal strong blocks is bounded byp≤q≤2p– 3 and that minimal strong blocks contain at least two nodes with indegree and outdegree equal

ISSN:0364-9024    

DOI:10.1002/jgt.3190030303

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

年代:1979

数据来源: WILEY

摘要:

AbstractWe show that the only nontrivial strongly orientable graphs for which every strong oreintation is Hamiltonian are complete graphs and cycles.

ISSN:0364-9024    

DOI:10.1002/jgt.3190030304

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

年代:1979

数据来源: WILEY

摘要:

AbstractThere are many results in the literature asserting that almost all or almost no graphs have some property. Our object is to develop a general logical theorem that will imply almost all of these results as corollaries. To this end, we propose the first‐order theory of almost all graphs by presenting Axiomnwhich states that for each sequence of2ndistinct vertices in a graph (u1, …,un,v1, …,vn), there exists another vertexwadjacent to eachu1and not adjacent to anyvi. A simple counting argument proves that for eachn, almost all graphs satisfy Axiomn. It is then shown that any sentence that can be stated in terms of these axioms is true in almost all graphs or in almost none. This has several immediate consequences, most of which have already been proved separately including: (1) For any graphH, almost all graphs have an induced subgraph isomorphic toH. (2) Almost no graphs are planar, or chordal, or line graphs. (3) Almost all grpahs are connected wiht diameter 2. It is also pointed out that these considerations extend to digraphs and to simplicial comp

ISSN:0364-9024    

DOI:10.1002/jgt.3190030305

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

年代:1979

数据来源: WILEY

摘要:

AbstractA vertexxin a subsetXof vertices of an undericted graph isredundantif its closed neighbourhood is contained in the union of closed neighborhoods of vertices ofX– {x}. In the context of a communications network, this means that any vertex that may receive communications fromXmay also be informed fromX– {x}.The irredundance numberir (G) is the minimum cardinality taken over all maximal sets of vertices having no redundancies. Thedomination numberγ(G) is the minimum cardinality taken over all dominating sets ofG, and theindependent domination number i(G) is the minimum cardinality taken over all maximal independent sets of vertices ofG. The paper contians results that relate these parameters. For example, we prove that for any graphG, ir (G)>γ(G)/2 and for any grpahGwithpvertices and no isolated vertices,i(G) ≤p‐γ(G) + 1 ‐ ⌈(

ISSN:0364-9024    

DOI:10.1002/jgt.3190030306

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

年代:1979

数据来源: WILEY

摘要:

AbstractLetGbe a connected graph of orderp≥ 2, with edge‐connectivity κ1(G) and minimum degree δ(G). It is shown her ethat in order to obtain the equality κ1(G) = δ(G), it is sufficient that, for each vertexxof minimum degree inG, the vertices in the neighbourhoodN(x) ofxhave sufficiently large degree sum. This result implies a previous result of Chartrand, which required that δ(G)

ISSN:0364-9024    

DOI:10.1002/jgt.3190030307

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

年代:1979

数据来源: WILEY

摘要:

AbstractA description is obtained for connected graphs in which a pointuis adjacent ofvonly ifuis adjacent to all points whose degree is greater than that ofv. The minimum number of lines in such a grpah with all points having degree at leastdis also determined. Finally, an application to communication systems is discussed.

ISSN:0364-9024    

DOI:10.1002/jgt.3190030308

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

年代:1979

数据来源: WILEY

摘要:

AbstractLetN(γ, γ′) denote the size of the smallest complete graph that cannot be edge‐partitioned into two parts embeddable in closed orientable sufaces of genera γ, γ′, respectively. Well‐known embedding theorems are used to obtain several infinite families of values ofN(γ, γ′). Some related small values ofN(γ, γ′)

ISSN:0364-9024    

DOI:10.1002/jgt.3190030309

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

年代:1979

数据来源: WILEY

摘要:

AbstractThe object of this paper is to show tht every planar graph of minimum valency 5 is reconstructible from its family of edge‐deleted subgraph

ISSN:0364-9024    

DOI:10.1002/jgt.3190030310

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

年代:1979

数据来源: WILEY

摘要:

AbstractA method is described of constructing a class of self‐complementary graphs, that includes a self‐complementary graph, containing noK5, with 41 vertices and a self‐complementary graph, containing noK7, with 113 vertices. The latter construction gives the improved Ramsey number lower boundr(7, 7)

ISSN:0364-9024    

DOI:10.1002/jgt.3190030311

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

年代:1979

数据来源: WILEY