Inequality Related to Vizing's Conjecture

Let $\gamma(G)$ denote the domination number of a graph $G$ and let $G\square H$ denote the Cartesian product of graphs $G$ and $H$. We prove that $\gamma(G)\gamma(H) \le 2 \gamma(G\square H)$ for all simple graphs $G$ and $H$.

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2000-05, Vol.7 (1)
Main Authors: Clark, W. Edwin, Suen, Stephen
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c134t-6b9ce999469da29edd670afabb2eae436585c352c3334ff4b728f2b54f4c46713
cites
container_end_page
container_issue 1
container_start_page
container_title The Electronic journal of combinatorics
container_volume 7
creator Clark, W. Edwin
Suen, Stephen
description Let $\gamma(G)$ denote the domination number of a graph $G$ and let $G\square H$ denote the Cartesian product of graphs $G$ and $H$. We prove that $\gamma(G)\gamma(H) \le 2 \gamma(G\square H)$ for all simple graphs $G$ and $H$.
doi_str_mv 10.37236/1542
format article
fullrecord <record><control><sourceid>crossref</sourceid><recordid>TN_cdi_crossref_primary_10_37236_1542</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>10_37236_1542</sourcerecordid><originalsourceid>FETCH-LOGICAL-c134t-6b9ce999469da29edd670afabb2eae436585c352c3334ff4b728f2b54f4c46713</originalsourceid><addsrcrecordid>eNpNj8tKxDAUQIMoOI7zD92IuKgmuTdJs5TiY2BAEHVbkvRGOtRWk8xi_HrxsXB1zurAYWwl-CUYCfpKKJQHbCG4MXVjpT7858fsJOct50JaqxbsYj3Rx86NQ9lXjzS6Qn1V5upl-Bym1_NctfO0pVB2iU7ZUXRjptUfl-z59uapva83D3fr9npTBwFYau1tIGstats7aanvteEuOu8lOULQqlEBlAwAgDGiN7KJ0iuMGFAbAUt29tsNac45Ueze0_Dm0r4TvPv5677_4Au1yUDO</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>Inequality Related to Vizing's Conjecture</title><source>Freely Accessible Science Journals - May need to register for free articles</source><creator>Clark, W. Edwin ; Suen, Stephen</creator><creatorcontrib>Clark, W. Edwin ; Suen, Stephen</creatorcontrib><description>Let $\gamma(G)$ denote the domination number of a graph $G$ and let $G\square H$ denote the Cartesian product of graphs $G$ and $H$. We prove that $\gamma(G)\gamma(H) \le 2 \gamma(G\square H)$ for all simple graphs $G$ and $H$.</description><identifier>ISSN: 1077-8926</identifier><identifier>EISSN: 1077-8926</identifier><identifier>DOI: 10.37236/1542</identifier><language>eng</language><ispartof>The Electronic journal of combinatorics, 2000-05, Vol.7 (1)</ispartof><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c134t-6b9ce999469da29edd670afabb2eae436585c352c3334ff4b728f2b54f4c46713</citedby></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27901,27902</link.rule.ids></links><search><creatorcontrib>Clark, W. Edwin</creatorcontrib><creatorcontrib>Suen, Stephen</creatorcontrib><title>Inequality Related to Vizing's Conjecture</title><title>The Electronic journal of combinatorics</title><description>Let $\gamma(G)$ denote the domination number of a graph $G$ and let $G\square H$ denote the Cartesian product of graphs $G$ and $H$. We prove that $\gamma(G)\gamma(H) \le 2 \gamma(G\square H)$ for all simple graphs $G$ and $H$.</description><issn>1077-8926</issn><issn>1077-8926</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2000</creationdate><recordtype>article</recordtype><recordid>eNpNj8tKxDAUQIMoOI7zD92IuKgmuTdJs5TiY2BAEHVbkvRGOtRWk8xi_HrxsXB1zurAYWwl-CUYCfpKKJQHbCG4MXVjpT7858fsJOct50JaqxbsYj3Rx86NQ9lXjzS6Qn1V5upl-Bym1_NctfO0pVB2iU7ZUXRjptUfl-z59uapva83D3fr9npTBwFYau1tIGstats7aanvteEuOu8lOULQqlEBlAwAgDGiN7KJ0iuMGFAbAUt29tsNac45Ueze0_Dm0r4TvPv5677_4Au1yUDO</recordid><startdate>20000524</startdate><enddate>20000524</enddate><creator>Clark, W. Edwin</creator><creator>Suen, Stephen</creator><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>20000524</creationdate><title>Inequality Related to Vizing's Conjecture</title><author>Clark, W. Edwin ; Suen, Stephen</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c134t-6b9ce999469da29edd670afabb2eae436585c352c3334ff4b728f2b54f4c46713</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2000</creationdate><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Clark, W. Edwin</creatorcontrib><creatorcontrib>Suen, Stephen</creatorcontrib><collection>CrossRef</collection><jtitle>The Electronic journal of combinatorics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Clark, W. Edwin</au><au>Suen, Stephen</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Inequality Related to Vizing's Conjecture</atitle><jtitle>The Electronic journal of combinatorics</jtitle><date>2000-05-24</date><risdate>2000</risdate><volume>7</volume><issue>1</issue><issn>1077-8926</issn><eissn>1077-8926</eissn><abstract>Let $\gamma(G)$ denote the domination number of a graph $G$ and let $G\square H$ denote the Cartesian product of graphs $G$ and $H$. We prove that $\gamma(G)\gamma(H) \le 2 \gamma(G\square H)$ for all simple graphs $G$ and $H$.</abstract><doi>10.37236/1542</doi></addata></record>
fulltext fulltext
identifier ISSN: 1077-8926
ispartof The Electronic journal of combinatorics, 2000-05, Vol.7 (1)
issn 1077-8926
1077-8926
language eng
recordid cdi_crossref_primary_10_37236_1542
source Freely Accessible Science Journals - May need to register for free articles
title Inequality Related to Vizing's Conjecture
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-30T23%3A13%3A30IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-crossref&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Inequality%20Related%20to%20Vizing's%20Conjecture&rft.jtitle=The%20Electronic%20journal%20of%20combinatorics&rft.au=Clark,%20W.%20Edwin&rft.date=2000-05-24&rft.volume=7&rft.issue=1&rft.issn=1077-8926&rft.eissn=1077-8926&rft_id=info:doi/10.37236/1542&rft_dat=%3Ccrossref%3E10_37236_1542%3C/crossref%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c134t-6b9ce999469da29edd670afabb2eae436585c352c3334ff4b728f2b54f4c46713%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true