Loading…
Outer independent Roman dominating functions in graphs
A Roman dominating function (RDF) on a graph G is a function satisfying the condition that every vertex u for which is adjacent to at least one vertex v for which . A function is an outer-independent Roman dominating function (OIRDF) on G if f is an RDF and is an independent set. The outer-independe...
Saved in:
| Published in: | International journal of computer mathematics 2017-12, Vol.94 (12), p.2547-2557 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites 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-c338t-9313776f9a93e683122ed0cc5ef9d4e7e4d0b91cbcddb4986b1a3f3d9f1c97c93 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c338t-9313776f9a93e683122ed0cc5ef9d4e7e4d0b91cbcddb4986b1a3f3d9f1c97c93 |
| container_end_page | 2557 |
| container_issue | 12 |
| container_start_page | 2547 |
| container_title | International journal of computer mathematics |
| container_volume | 94 |
| creator | Abdollahzadeh Ahangar, Hossein Chellali, Mustapha Samodivkin, Vladimir |
| description | A Roman dominating function (RDF) on a graph G is a function
satisfying the condition that every vertex u for which
is adjacent to at least one vertex v for which
. A function
is an outer-independent Roman dominating function (OIRDF) on G if f is an RDF and
is an independent set. The outer-independent Roman domination number
is the minimum weight of an OIRDF on G. In this paper, we initiate the study of the outer-independent Roman domination number in graphs. We first show that determining the number
is NP-complete for bipartite graphs. Then we present lower and upper bounds on
. Moreover, we characterize graphs with small or large outer-independent Roman domination number. |
| doi_str_mv | 10.1080/00207160.2017.1301437 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_infor</sourceid><recordid>TN_cdi_proquest_journals_1964122084</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>1964122084</sourcerecordid><originalsourceid>FETCH-LOGICAL-c338t-9313776f9a93e683122ed0cc5ef9d4e7e4d0b91cbcddb4986b1a3f3d9f1c97c93</originalsourceid><addsrcrecordid>eNp9kEtLAzEUhYMoWKs_QRhwPfVmMk0mO6X4gkJBdB0yedSUTjImGaT_3hlat27u2XznXPgQusWwwNDAPUAFDFNYVIDZAhPANWFnaIah4iVUdHmOZhNTTtAlukppBwANZ3SG6GbIJhbOa9Ob8fhcvIdO-kKHznmZnd8WdvAqu-DTiBXbKPuvdI0urNwnc3PKOfp8fvpYvZbrzcvb6nFdKkKaXHKCCWPUcsmJoQ3BVWU0KLU0luvaMFNraDlWrdK6rXlDWyyJJZpbrDhTnMzR3XG3j-F7MCmLXRiiH18KzGk97kFTj9TySKkYUorGij66TsaDwCAmReJPkZgUiZOisfdw7DlvQ-zkT4h7LbI87EO0UXrlkiD_T_wCoZ5svg</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1964122084</pqid></control><display><type>article</type><title>Outer independent Roman dominating functions in graphs</title><source>Taylor and Francis Science and Technology Collection</source><creator>Abdollahzadeh Ahangar, Hossein ; Chellali, Mustapha ; Samodivkin, Vladimir</creator><creatorcontrib>Abdollahzadeh Ahangar, Hossein ; Chellali, Mustapha ; Samodivkin, Vladimir</creatorcontrib><description>A Roman dominating function (RDF) on a graph G is a function
satisfying the condition that every vertex u for which
is adjacent to at least one vertex v for which
. A function
is an outer-independent Roman dominating function (OIRDF) on G if f is an RDF and
is an independent set. The outer-independent Roman domination number
is the minimum weight of an OIRDF on G. In this paper, we initiate the study of the outer-independent Roman domination number in graphs. We first show that determining the number
is NP-complete for bipartite graphs. Then we present lower and upper bounds on
. Moreover, we characterize graphs with small or large outer-independent Roman domination number.</description><identifier>ISSN: 0020-7160</identifier><identifier>EISSN: 1029-0265</identifier><identifier>DOI: 10.1080/00207160.2017.1301437</identifier><language>eng</language><publisher>Abingdon: Taylor & Francis</publisher><subject>Graphs ; Mathematical functions ; Minimum weight ; outer-independent Roman domination ; Roman domination ; Upper bounds</subject><ispartof>International journal of computer mathematics, 2017-12, Vol.94 (12), p.2547-2557</ispartof><rights>2017 Informa UK Limited, trading as Taylor & Francis Group 2017</rights><rights>2017 Informa UK Limited, trading as Taylor & Francis Group</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c338t-9313776f9a93e683122ed0cc5ef9d4e7e4d0b91cbcddb4986b1a3f3d9f1c97c93</citedby><cites>FETCH-LOGICAL-c338t-9313776f9a93e683122ed0cc5ef9d4e7e4d0b91cbcddb4986b1a3f3d9f1c97c93</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27923,27924</link.rule.ids></links><search><creatorcontrib>Abdollahzadeh Ahangar, Hossein</creatorcontrib><creatorcontrib>Chellali, Mustapha</creatorcontrib><creatorcontrib>Samodivkin, Vladimir</creatorcontrib><title>Outer independent Roman dominating functions in graphs</title><title>International journal of computer mathematics</title><description>A Roman dominating function (RDF) on a graph G is a function
satisfying the condition that every vertex u for which
is adjacent to at least one vertex v for which
. A function
is an outer-independent Roman dominating function (OIRDF) on G if f is an RDF and
is an independent set. The outer-independent Roman domination number
is the minimum weight of an OIRDF on G. In this paper, we initiate the study of the outer-independent Roman domination number in graphs. We first show that determining the number
is NP-complete for bipartite graphs. Then we present lower and upper bounds on
. Moreover, we characterize graphs with small or large outer-independent Roman domination number.</description><subject>Graphs</subject><subject>Mathematical functions</subject><subject>Minimum weight</subject><subject>outer-independent Roman domination</subject><subject>Roman domination</subject><subject>Upper bounds</subject><issn>0020-7160</issn><issn>1029-0265</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2017</creationdate><recordtype>article</recordtype><recordid>eNp9kEtLAzEUhYMoWKs_QRhwPfVmMk0mO6X4gkJBdB0yedSUTjImGaT_3hlat27u2XznXPgQusWwwNDAPUAFDFNYVIDZAhPANWFnaIah4iVUdHmOZhNTTtAlukppBwANZ3SG6GbIJhbOa9Ob8fhcvIdO-kKHznmZnd8WdvAqu-DTiBXbKPuvdI0urNwnc3PKOfp8fvpYvZbrzcvb6nFdKkKaXHKCCWPUcsmJoQ3BVWU0KLU0luvaMFNraDlWrdK6rXlDWyyJJZpbrDhTnMzR3XG3j-F7MCmLXRiiH18KzGk97kFTj9TySKkYUorGij66TsaDwCAmReJPkZgUiZOisfdw7DlvQ-zkT4h7LbI87EO0UXrlkiD_T_wCoZ5svg</recordid><startdate>20171202</startdate><enddate>20171202</enddate><creator>Abdollahzadeh Ahangar, Hossein</creator><creator>Chellali, Mustapha</creator><creator>Samodivkin, Vladimir</creator><general>Taylor & Francis</general><general>Taylor & Francis Ltd</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20171202</creationdate><title>Outer independent Roman dominating functions in graphs</title><author>Abdollahzadeh Ahangar, Hossein ; Chellali, Mustapha ; Samodivkin, Vladimir</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c338t-9313776f9a93e683122ed0cc5ef9d4e7e4d0b91cbcddb4986b1a3f3d9f1c97c93</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2017</creationdate><topic>Graphs</topic><topic>Mathematical functions</topic><topic>Minimum weight</topic><topic>outer-independent Roman domination</topic><topic>Roman domination</topic><topic>Upper bounds</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Abdollahzadeh Ahangar, Hossein</creatorcontrib><creatorcontrib>Chellali, Mustapha</creatorcontrib><creatorcontrib>Samodivkin, Vladimir</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>International journal of computer mathematics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Abdollahzadeh Ahangar, Hossein</au><au>Chellali, Mustapha</au><au>Samodivkin, Vladimir</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Outer independent Roman dominating functions in graphs</atitle><jtitle>International journal of computer mathematics</jtitle><date>2017-12-02</date><risdate>2017</risdate><volume>94</volume><issue>12</issue><spage>2547</spage><epage>2557</epage><pages>2547-2557</pages><issn>0020-7160</issn><eissn>1029-0265</eissn><abstract>A Roman dominating function (RDF) on a graph G is a function
satisfying the condition that every vertex u for which
is adjacent to at least one vertex v for which
. A function
is an outer-independent Roman dominating function (OIRDF) on G if f is an RDF and
is an independent set. The outer-independent Roman domination number
is the minimum weight of an OIRDF on G. In this paper, we initiate the study of the outer-independent Roman domination number in graphs. We first show that determining the number
is NP-complete for bipartite graphs. Then we present lower and upper bounds on
. Moreover, we characterize graphs with small or large outer-independent Roman domination number.</abstract><cop>Abingdon</cop><pub>Taylor & Francis</pub><doi>10.1080/00207160.2017.1301437</doi><tpages>11</tpages></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0020-7160 |
| ispartof | International journal of computer mathematics, 2017-12, Vol.94 (12), p.2547-2557 |
| issn | 0020-7160 1029-0265 |
| language | eng |
| recordid | cdi_proquest_journals_1964122084 |
| source | Taylor and Francis Science and Technology Collection |
| subjects | Graphs Mathematical functions Minimum weight outer-independent Roman domination Roman domination Upper bounds |
| title | Outer independent Roman dominating functions in graphs |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-08T19%3A07%3A21IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_infor&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Outer%20independent%20Roman%20dominating%20functions%20in%20graphs&rft.jtitle=International%20journal%20of%20computer%20mathematics&rft.au=Abdollahzadeh%20Ahangar,%20Hossein&rft.date=2017-12-02&rft.volume=94&rft.issue=12&rft.spage=2547&rft.epage=2557&rft.pages=2547-2557&rft.issn=0020-7160&rft.eissn=1029-0265&rft_id=info:doi/10.1080/00207160.2017.1301437&rft_dat=%3Cproquest_infor%3E1964122084%3C/proquest_infor%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c338t-9313776f9a93e683122ed0cc5ef9d4e7e4d0b91cbcddb4986b1a3f3d9f1c97c93%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1964122084&rft_id=info:pmid/&rfr_iscdi=true |