×

Irredundancy in circular arc graphs. (English) Zbl 0783.05059

An open neighbourhood of a vertex \(x\) in an undirected graph \(G\) is the set \(N(x)\) of all vertices adjacent to \(x\) in \(G\); its closed neighbourhood is \(N[x]=N(x) \cup \{x\}\). For a set \(S\) of vertices set \(N(S)=\bigcup_{x \in S}N(x)\) and \(N[S]=\bigcup_{x \in S} N[x]\). A subset \(X\) of the vertex set of \(G\) is called irredundant (or open-open irredundant, or closed-open irredundant, or open-closed irredundant), if for every \(x \in X\) we have \(N[x]-N \bigl[ X-\{x\} \bigr] \neq \varnothing\) (or \(N(x)-N \bigl(X-\{x\} \bigr) \neq \varnothing\), or \(N[x]- N \bigl( X-\{x\} \bigr) \neq \varnothing\), or \(N(x)-N \bigl[ X-\{x\} \bigr] \neq \varnothing\), respectively). The maximum cardinalities of an irredundant set, an open-open irredundant set, a closed-open irredundant set, an open-closed irredundant set are denoted by \(\text{IR}(G)\), \(\text{OOIR}(G)\), \(\text{COIR}(G)\), \(\text{OCIR}(G)\), respectively. These numbers are studied for circular arc graphs; a circular arc graph is a graph whose vertices can be represented by arcs of a circle, two vertices being adjacent if and only if the corresponding arcs have a nonempty intersection.

MSC:

05C35 Extremal problems in graph theory
05C99 Graph theory
Full Text: DOI

References:

[1] Bertossi, A. A.; Gori, A., Total domination and irredundance in weighted interval graphs, SIAM J. Discrete Math., 1, 317-327 (1988) · Zbl 0648.05041
[2] Bollobás, B.; Cockayne, E. J., Graph theoretic parameters concerning domination, independence and irredundance, J. Graph Theory, 3, 241-249 (1979) · Zbl 0418.05049
[3] Bollobás, B.; Cockayne, E. J., On the irredundance number and maximum degree of a graph, Discrete Math., 49, 197-199 (1984) · Zbl 0539.05056
[4] Cockayne, E. J.; Favoron, O.; Payan, C.; Thomason, A., Contributions to the theory of domination, independence and irredundance in graphs, Discrete Math., 33, 249-258 (1981) · Zbl 0471.05051
[5] Cockayne, E. J.; Hedetniemi, S. T., Independence graphs, Proceedings of 5th Southeastern Conference on Combinatorics, Graph Theory and Computing, Utilitas Math, 471-491 (1974) · Zbl 0305.05114
[6] Cockayne, E. J.; Hedetniemi, S. T.; Miller, D. J., Properties of hereditary hypergraphs and middle graphs, Canad. Math. Bull., 21, 461-468 (1978) · Zbl 0393.05044
[7] Farley, A. M.; Proskurowski, A., Computing the maximum order of an open irredundant set in a tree, Congr. Numer., 41, 219-228 (1984) · Zbl 0546.05034
[8] Farley, A. M.; Shacham, N., Senders in broadcast networks: open-irredundancy in graphs, Congr. Numer., 38, 47-57 (1983) · Zbl 0539.94040
[9] Favaron, O., Stability, domination and irredundance in a graph, J. Graph Theory, 10, 429-438 (1986) · Zbl 0612.05056
[10] Favaron, O., On the open irredundance in a graph, Congr. Numer., 66, 316-318 (1988) · Zbl 0673.05083
[11] Fink, J. F.; Jacobson, M. S., \(n\)-domination, (Graphs, Graph Theory with Applications to Algorithms and Computer Science (1985), Wiley: Wiley New York), 283-300, (Kalamazoo, MI) · Zbl 0573.05049
[12] Fricke, G.; Hedetniemi, S. M.; Laskar, R., Open-irredundance in trees (1989), Manuscript
[13] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[14] Golumbic, M. C.; Hammer, P. L., Stability in circular arc graphs, J. Algorithms, 9, 314-320 (1988) · Zbl 0651.68083
[15] S.M. Hedetniemi, private communication, 1989.; S.M. Hedetniemi, private communication, 1989.
[16] Hedetniemi, S. T.; Laskar, R. C.; Pfaff, J., Irredundance in graphs: a survey, (Proceedings 16th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congr. Numer., 48 (1985)), 183-193 · Zbl 0647.05060
[17] M.S. Jacobson and K. Peters, Chordal graphs and upper irredundance, upper domination and independence, Discrete Math., to appear.; M.S. Jacobson and K. Peters, Chordal graphs and upper irredundance, upper domination and independence, Discrete Math., to appear. · Zbl 0744.05063
[18] König, D., Graphen und Matrizen, Math. Fig. Lopok., 38, 116-119 (1931) · JFM 57.1340.04
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.