Further results on independence in direct-product graphs
For a graph G, let alpha(G) and tau(G) denote the independence number of G and the matching number of G, respectively. Further, let G x H denote the direct product (also known as Kronecker product, cardinal product, tensor product., categorical product and graph conjunction) of graphs G and H. It is...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Charles Babbage Res Ctr
2000
|
| Subjects: | |
| Online Access: | http://shdl.mmu.edu.my/2710/ http://shdl.mmu.edu.my/2710/1/Further%20results%20on%20independence%20in%20direct-product%20graphs.pdf |
| _version_ | 1848790129971298304 |
|---|---|
| author | Jha, P. K. |
| author_facet | Jha, P. K. |
| author_sort | Jha, P. K. |
| building | MMU Institutional Repository |
| collection | Online Access |
| description | For a graph G, let alpha(G) and tau(G) denote the independence number of G and the matching number of G, respectively. Further, let G x H denote the direct product (also known as Kronecker product, cardinal product, tensor product., categorical product and graph conjunction) of graphs G and H. It is known that alpha(G x H) greater than or equal to max{alpha(G) . \H\, alpha(H) . \G\} =: alpha(G x H) and that tau(G x H) greater than or equal to 2 . tau(G) . tau(H) =: tau(G X H). It is shown that an equality/inequality between ct and ct is independent of an equality/inequality between tau and tau. Further, several results are presented on the existence of a complete matching in each of the two connected components of the direct product of two bipartite graphs. Additional results include an upper bound on alpha(G x H) that is achievable in certain cases. |
| first_indexed | 2025-11-14T18:07:43Z |
| format | Article |
| id | mmu-2710 |
| institution | Multimedia University |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T18:07:43Z |
| publishDate | 2000 |
| publisher | Charles Babbage Res Ctr |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | mmu-27102013-11-11T04:24:19Z http://shdl.mmu.edu.my/2710/ Further results on independence in direct-product graphs Jha, P. K. QA Mathematics For a graph G, let alpha(G) and tau(G) denote the independence number of G and the matching number of G, respectively. Further, let G x H denote the direct product (also known as Kronecker product, cardinal product, tensor product., categorical product and graph conjunction) of graphs G and H. It is known that alpha(G x H) greater than or equal to max{alpha(G) . \H\, alpha(H) . \G\} =: alpha(G x H) and that tau(G x H) greater than or equal to 2 . tau(G) . tau(H) =: tau(G X H). It is shown that an equality/inequality between ct and ct is independent of an equality/inequality between tau and tau. Further, several results are presented on the existence of a complete matching in each of the two connected components of the direct product of two bipartite graphs. Additional results include an upper bound on alpha(G x H) that is achievable in certain cases. Charles Babbage Res Ctr 2000-07 Article NonPeerReviewed text en http://shdl.mmu.edu.my/2710/1/Further%20results%20on%20independence%20in%20direct-product%20graphs.pdf Jha, P. K. (2000) Further results on independence in direct-product graphs. Ars Combinatoria, 56. pp. 15-24. ISSN 0381-7032 |
| spellingShingle | QA Mathematics Jha, P. K. Further results on independence in direct-product graphs |
| title | Further results on independence in direct-product graphs |
| title_full | Further results on independence in direct-product graphs |
| title_fullStr | Further results on independence in direct-product graphs |
| title_full_unstemmed | Further results on independence in direct-product graphs |
| title_short | Further results on independence in direct-product graphs |
| title_sort | further results on independence in direct-product graphs |
| topic | QA Mathematics |
| url | http://shdl.mmu.edu.my/2710/ http://shdl.mmu.edu.my/2710/1/Further%20results%20on%20independence%20in%20direct-product%20graphs.pdf |