Uma estrela é um tipo especial de árvore. Como acontece com qualquer árvore, as estrelas podem ser codificados por uma sequência Prüfer; A sequência Prüfer para uma estrela K1,k consiste de k − 1 cópias do vértice central[4]. Uma árvore pode ser vista como um conjunto de estrelas (pares ou ímpares) ligadas pelos pontos centrais[5].
Diversos grafos invariantes são definidos em termos de estrelas. Arboricidade de estrela é o menor número de florestas que um grafo pode ser particionado em tal modo que cada árvore em cada floresta é uma estrela[6], e o número cromático de estrela de um grafo é o menor número de cores necessário para colorir seus vértices de tal forma que cada duas classes de coloração, juntas, formam um subgrafo em que todos os componentes conectados são estrelas[7]. Os grafos de comprimento de ramo 1 são exatamente os grafos em que cada componente conectado é uma estrela[8].
Outras aplicações
O conjunto de distâncias entre os vértices de uma garra fornece um exemplo de um espaço métrico finito, que não pode ser incorporado isometricamente em um espaço euclideano de qualquer dimensão[9].
↑BOAVENTURA NETTO, Paulo Oswaldo (2001). Grafos. Teoria, Modelos Algoritmos. São Paulo: Edgard Blücher. p. 27. ISBN85-212-0292-X
↑FAUDREE, Ralph; FLANDRIN, Evelyne; RYJÁčEK, Zdeněk (1997). «Claw-free graphs — A survey». Discrete Mathematics. 164 (1–3). pp. 87–147. doi:10.1016/S0012-365X(96)00045-3 !CS1 manut: Nomes múltiplos: lista de autores (link).
↑Chudnovsky, Maria; Seymour, Paul (2005), «The structure of claw-free graphs», Surveys in combinatorics 2005(PDF), London Math. Soc. Lecture Note Ser., 327, Cambridge: Cambridge Univ. Press, pp. 153–171, consultado em 25 de outubro de 2010, cópia arquivada (PDF) em |arquivourl= requer |arquivodata= (ajuda)🔗.
↑
Gottlieb, J.; Julstrom, B. A.; Rothlauf, F.; Raidl, G. R. (2001), «Prüfer numbers: A poor representation of spanning trees for evolutionary search», Proc. Genetic and Evolutionary Computation Conference(PDF), Morgan Kaufmann, pp. 343–350, consultado em 25 de outubro de 2010, cópia arquivada (PDF) em |arquivourl= requer |arquivodata= (ajuda)🔗
↑BARBOSA, Ruy Madsen (1975). Combinatória e Grafos. 2. São Paulo: Livraria Nobel. p. 196
↑Hakimi, S. L.; Mitchem, J.; Schmeichel, E. E. (1996), «Star arboricity of graphs», Discrete Math., 149: 93–98, doi:10.1016/0012-365X(94)00313-8
↑FERTIN, Guillaume; RASPAUD, André; REED, Bruce (2004). «Star coloring of graphs». Journal of Graph Theory. 47 (3). pp. 163–182. doi:10.1002/jgt.20029 !CS1 manut: Nomes múltiplos: lista de autores (link)
↑ROBERTSON, Neil; SEYMOUR, Paul D. (1991). «Graph minors. X. Obstructions to tree-decomposition». Journal of Combinatorial Theory. 52 (2). pp. 153–190. doi:10.1016/0095-8956(91)90061-N !CS1 manut: Nomes múltiplos: lista de autores (link)
↑Linial, Nathan (2002), «Finite metric spaces–combinatorics, geometry and algorithms», Proc. International Congress of Mathematicians, Beijing, 3, pp. 573–586, Arxiv