|
|
Bimonthly Since 1986 |
ISSN 1004-9037
|
|
|
|
|
Publication Details |
Edited by: Editorial Board of Journal of Data Acquisition and Processing
P.O. Box 2704, Beijing 100190, P.R. China
Sponsored by: Institute of Computing Technology, CAS & China Computer Federation
Undertaken by: Institute of Computing Technology, CAS
Published by: SCIENCE PRESS, BEIJING, CHINA
Distributed by:
China: All Local Post Offices
|
|
|
|
|
|
|
|
|
|
Abstract
Let G=(V,E) be an undirected connected graph. Let S be a minimum detour edge semi-toll set (〖EST〗_dn-set) of G. A subset M⊆S is said to be a forcing subset of S if S is the unique 〖EST〗_dn-set containing M. The forcing E〖ST〗_dn number f_(〖EST〗_dn ) (S) of S in G is the minimum cardinality of a forcing subset for S. The forcing detour edge semi-toll number f_(〖EST〗_dn ) (G) of G is the minimum cardinality of f_(〖EST〗_dn ) (S), where the minimum is taken over all 〖EST〗_dn-sets S of G . It proved that 0 ≤f_(〖EST〗_dn ) (G) ≤〖EST〗_dn (G) .Some general properties satisfied by this concept are studied. The forcing detour edge semi- toll number of some standard graphs are determined. Necessary and sufficient conditions for f_(〖EST〗_dn ) (G) to be 0 or 1 are characterized. It is shown that every pair of integers a and b with 0≤a≤b, there exists a connected graph G such that f_(〖EST〗_dn ) (G)=a and E〖ST〗_dn (G)=b. Also it is shown that for every pair of integers a and b with 0≤a≤b, there exists a connected graph G such that f_(〖EST〗_dn ) (G) = a and f_dn (G)=b.
Keyword
detour number, forcing detour number, tolled walk, detour edge semi-toll number, forcing detour edge semi toll number.
PDF Download (click here)
|
|
|
|
|