Roman domination in graphs. (Q1427467): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Bohdan Zelinka / rank | |||
Property / reviewed by | |||
Property / reviewed by: Bohdan Zelinka / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.disc.2003.06.004 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1984228559 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4004078 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5461685 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Independent domination in chordal graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4368728 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A characterization of Roman trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Defendens Imperium Romanum: A Classical Problem in Military Strategy / rank | |||
Normal rank |
Latest revision as of 15:27, 6 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Roman domination in graphs. |
scientific article |
Statements
Roman domination in graphs. (English)
0 references
14 March 2004
0 references
The paper studies the Roman domination in graphs. It is a special kind of domination whose introduction was motivated by military rules of the ancient Roman Empire. Let \(G\) be a graph with vertex set \(V(G)\), and let \(f: V(G)\to \{0,1,2\}\). If to each vertex \(v\) with \(f(v)= 0\) there exists a vertex \(w\) with \(f(w)= 2\) adjacent to \(v\), then \(f\) is called a Roman dominating function on \(G\). Its weight is \(w(f)= \sum_{x\in V(G)}f(x)\). The minimum weight of a Roman dominating function on \(G\) is the Roman domination number \(\gamma_R(G)\) of \(G\). Properties of Roman dominating functions on \(G\) are described and some bounds for \(\gamma_R(G)\) are found. For some types of graphs, including paths and cycles, exact values are found. Special attention is paid to graphs \(G\) with \(\gamma_R(G)\leq \gamma(G)+ 2\), where \(\gamma(G)\) is the well-known domination number of \(G\). Graphs with \(\gamma_R(G)= 2\gamma(G)\) are called Roman graphs and are studied. At the end of the paper open problems are suggested.
0 references
Roman dominating function
0 references
Roman domination number
0 references
Roman graphs
0 references
facilities
0 references