Jha, P. K.
(2000)
*Further results on independence in direct-product graphs.*
Ars Combinatoria, 56.
pp. 15-24.
ISSN 0381-7032

Text
Further results on independence in direct-product graphs.pdf Restricted to Repository staff only Download (7MB) |

## Abstract

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.

Item Type: | Article |
---|---|

Subjects: | Q Science > QA Mathematics |

Divisions: | Faculty of Information Science and Technology (FIST) |

Depositing User: | Ms Rosnani Abd Wahab |

Date Deposited: | 09 Sep 2011 02:42 |

Last Modified: | 11 Nov 2013 04:24 |

URI: | http://shdl.mmu.edu.my/id/eprint/2710 |

### Actions (login required)

View Item |