Premium
Orthogonal ( g, f )‐factorizations in networks
Author(s) -
Lam Peter Che Bor,
Liu Guizhen,
Li Guojun,
Shiu Wai Chee
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/1097-0037(200007)35:4<274::aid-net6>3.0.co;2-6
Subject(s) - combinatorics , graph , factorization , mathematics , integer (computer science) , discrete mathematics , computer science , algorithm , programming language
Let G = ( V, E ) be a graph and let g and f be two integer‐valued functions defined on V such that k ≤ g ( x ) ≤ f ( x ) for all x ∈ V . Let H 1 , H 2 , …, H k be subgraphs of G such that | E ( H i )| = m , 1 ≤ i ≤ k , and V ( H i ) ∩ V ( H j ) = 0 when i ≠ j . In this paper, it is proved that every ( mg + m − 1, mf − m + 1)‐graph G has a ( g, f )‐factorization orthogonal to H i for i = 1, 2, …, k and shown that there are polynomial‐time algorithms to find the desired ( g, f )‐factorizations. © 2000 John Wiley & Sons, Inc.