摘要:

AbstractFor a given graphical invariant π, a sequence (ao, a1,…, an) of positive integers is said to be π‐feasible if there exists a graphGwith distinguished vertices ν1, ν2,…, νnsuch that π(G)= aoand π(G −ν1−ν2−…−νi) = aifor i = 1, 2,…,n. In this paper, we investigate π‐feasible sequences for the irredundance, domination, and i

ISSN:0028-3045    

DOI:10.1002/net.3230250102

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

年代:1995

数据来源: WILEY

摘要:

AbstractThe stability of a (communication or transportation) network composed of (processing) nodes and (communication or transportation) links is of prime importance to network designers. As the network begins losing links or nodes, eventually, there is a loss in its effectiveness. Thus, it is desirable that networks be constructed to be as stable as possible, not only with respect to the initial disruption, but also with respect to the possible reconfiguration of the network after disruption. Many graph theoretical parameters have been used in the past to describe the stability of networks, including the vertex‐connectivity and edge‐connectivity, toughness and edge‐toughness, integrity and edge‐integrity, and tenacity. In this paper, we study the edge‐tenacity of graphs. We will be primarily interested in edge‐tenacious graphs, which can be considered very stable and are somewhat analogous in edge‐tenacity to honest graphs in edge‐integrity. We prove several results about edge‐tenacious graphs as well as find numerous classes of edge

ISSN:0028-3045    

DOI:10.1002/net.3230250103

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

年代:1995

数据来源: WILEY

摘要:

AbstractIn this paper, we consider the integral multicommodity flow problem on directed graphs underlying two classes of multistage interconnection networks. In one direction, we consider three‐stage networks. Using existing results on (g,f)‐factors of bipartite graphs, we show sufficient and necessary conditions for the existence of a solution when the network has at most two secondary switches. In contrast, the problem is shown to be NP‐complete if the network has three or more secondaries. In a second direction, we introduce a recursive class of networks that includes multistage hypercubic networks (such as the omega network, the indirect binaryn‐cube, and the generalized cube network) as a proper subset. Networks in the new class may have an arbitrary number of stages. Moreover, each stage may contain identical switches of any arbitrary size. The notion of extrastage networks is extended to the new class, and the problem is shown to have polynomial time solutions onr‐stage networks wherer= 3 or where each link has a unit capacity andr ≥3. The latter result implies an efficient algorithm for deciding admissible permutations on conventional extrastage hypercubic networks. In contrast, we show that the multicommodity flow problem is NP‐complete on extrastage networks, even ifr= 6, each link has an integral capacity ≤ 3, and all flow de

ISSN:0028-3045    

DOI:10.1002/net.3230250104

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

年代:1995

数据来源: WILEY

摘要:

AbstractThe optimality of the length of a test sequence for a given finite‐state machine can be determined only with respect to the class of test sequences that employ the same number and type of state identification/verification (SIV) sequences and satisfy the same requirements for the starting and terminating states. Given a certain number and type of SIV sequences, we identify three different types of optimality for test sequences: Type11requires test sequences to begin and end at the initial state; Type1yrequires only that test sequences begin at the initial state; and Typexyimposes no requirements whatsoever on the starting and terminating states. Based on these definitions, we investigate the case where Unique Input Output (UIO) sequences are given as SIV sequences and derive lower bounds for the length of test sequences of Type11, Type1y, and Typex

ISSN:0028-3045    

DOI:10.1002/net.3230250105

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

年代:1995

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230250106

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

年代:1995

数据来源: WILEY