Star saturation number of random graphs

For a given graph $F$, the $F$-saturation number of a graph $G$ is the minimum number of edges in an edge-maximal $F$-free subgraph of $G$. Recently, the $F$-saturation number of the Erd?s–Rényi random graph $\mathbb{G}(n,p)$ has been determined asymptotically for any complete graph $F$. In this paper, we give an asymptotic formula for the $F$-saturation number of $\mathbb{G}(n,p)$ when $F$ is a star graph.     

On the weak 2-coloring number of planar graphs

For a graph $G=(V,E)$, a total ordering L on V, and a vertex $v\in V$, let ${\mathrm{Wcol}}_2[G,L,v]$ be the set of vertices $w\in V$ for which there is a path from v to w whose length is 0, 1 or 2 and whose L-least vertex is w. The weak 2-coloring number ${\mathrm{wcol}}_2(G)$ of G is the least k such that there is a total ordering L on V with $|{\mathrm{Wcol}}_2[G,L,v]|\le k$ for all vertices $v\in V$. We improve the known upper bound on the weak 2-coloring number of planar graphs from 28 to 23. As the weak 2-coloring number is the best known upper bound on the star list chromatic number of planar graphs, this bound is also improved.     

Sm ∨ Kn,n的边色数和均匀全色数

本文得到了m 1阶星和完全等二部图联图的边色数和均匀全色数.     

Multitriangulations as Complexes of Star Polygons

Maximal (k+1)-crossing-free graphs on a planar point set in convex position, that is, k-triangulations, have received attention in recent literature, motivated by several interpretations of them. We introduce a new way of looking at k-triangulations, namely as complexes of star polygons. With this tool we give new, direct proofs of the fundamental properties of k-triangulations, as well as some new results. This interpretation also opens up new avenues of research that we briefly explore in the last section. This paper was written while the first author was visiting the second one via an internship agreement between the école Normale Supérieure and the University of Cantabria. Research of both authors was also funded by grant MTM2005-08618-C02-02 of the Spanish Ministry of Education and Science. A short version of this paper was presented at the FPSAC 08 conference.     

Embedding cycles of various lengths into star graphs with both edge and vertex faults

The n-dimensional star graph S_n is an attractive alternative to the hypercube graph and is a bipartite graph with two partite sets of equal size. Let F_v and F_e be the sets of faulty vertices and faulty edges of S_n, respectively. We prove that S_n − F_v − F_e contains a fault-free cycle of every even length from 6 to n! − 2∣F_v∣ with ∣F_v∣ + ∣F_e∣ ? n − 3 for every n ? 4. We also show that S_n − F_v − F_e contains a fault-free path of length n! − 2∣F_v∣ − 1 (respectively, n! − 2∣F_v∣ − 2) between two arbitrary vertices of S_n in different partite sets (respectively, the same partite set) with ∣F_v∣ + ∣F_e∣ ? n − 3 for every n ? 4.     

Cycle embedding in star graphs with conditional edge faults

Among the various interconnection networks, the star graph has been an attractive one. In this paper, we consider the cycle embedding problem in star graphs with conditional edge faults. We show that there exist cycles of all even lengths from 6 to n! in an n-dimensional star graph with ?2n-7 edge faults in which each vertex is incident with at least two healthy edges for n?4.     

The Star Chromatic Numbers of Some Planar Graphs Derived from Wheels

The notion of the star chromatic number of a graph is a generalization of the chromatic number. In this paper, we calculate the star chromatic numbers of three infinite families of planar graphs. The first two families are derived from a 3-or 5-wheel by subdivisions, their star chromatic numbers being 2+2/(2n + 1), 2+3/(3n + 1), and 2+3(3n−1), respectively. The third family of planar graphs are derived from n odd wheels by Hajos construction with star chromatic numbers 3 + 1/n, which is a generalization of one result of Gao et al. Received September 21, 1998, Accepted April 9, 2001.     

由轮图导出的某些平面图类的星色数

图的星色数是通常色数概念的推广.本文求出了几类由轮图导出的平面图的星色数.前两类是由3-或5-轮图经细分等构造出的,其星色数分别为2+2/(2n+1),2+3/(3n+1)和2+3/(3n-1).第三类平面图是由n-轮图经过Hajos构造得到的,其星色数为3+1/n.本类图的星色数结果推广了已有结论.     

Cycle embedding in star graphs with more conditional faulty edges

The star graph is one of the most attractive interconnection networks. The cycle embedding problem is widely discussed in many networks, and edge fault tolerance is an important issue for networks since edge failures may occur when a network is put into use. In this paper, we investigate the cycle embedding problem in star graphs with conditional faulty edges. We show that there exist fault-free cycles of all even lengths from 6 to n! in any n-dimensional star graph S_n (n ? 4) with ?3n − 10 faulty edges in which each node is incident with at least two fault-free edges. Our result not only improves the previously best known result where the number of tolerable faulty edges is up to 2n − 7, but also extends the result that there exists a fault-free Hamiltonian cycle under the same condition.     

On properties of cell matrices

In this paper properties of cell matrices are studied. A determinant of such a matrix is given in a closed form. In the proof a general method for determining a determinant of a symbolic matrix with polynomial entries, based on multivariate polynomial Lagrange interpolation, is outlined. It is shown that a cell matrix of size n>1 has exactly one positive eigenvalue. Using this result it is proven that cell matrices are (Circum-)Euclidean Distance Matrices ((C)EDM), and their generalization, k-cell matrices, are CEDM under certain natural restrictions. A characterization of k-cell matrices is outlined.     

一类多重联图的邻点可区别E-全染色

设G（V,E）是一个简单图,k是一个正整数,f是一个V（G）∪E（G）到{1,2,…,k]．的映射．如果Au,v∈E（G）,则f（u）≠f（v）,f（u）≠f（uv）,f（v）≠f（uv）,C（u）≠C（v）,其中C（u）={f（u））U{f（uv）｜uv∈E（G））．称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别B全色数．本文给出了星、路、圈间的多重联图的邻点可区别E-全色数．     

Star图互连网络的容错性分析

限制连通度和限制容错直径是衡量互连网络可靠性的两个重要参数。当考察这两个参数时，总假设网络中和一台计算机相连接的所有计算机不会同时出现故障。该文证明了Star图互连网络的极小分离集和极小限制分离集的唯一性，然后得到了Star图的限制连通度是2n-4，当n=3,5和n≥7时，它的限制容错直径是|_3(n-1)/2_|+2，对于n =4, 6，限制容错直径是|_3(n-1)/2_|+3，即限制容错直径只比它的容错直径大1。     

List star chromatic index of sparse graphs

A star edge-coloring of a graph $G$ is a proper edge coloring such that every 2-colored connected subgraph of $G$ is a path of length at most 3. For a graph $G$, let the list star chromatic index of $G$, $c{h}_s^{\prime }\left(G\right)$, be the minimum $k$ such that for any $k$-uniform list assignment $L$ for the set of edges, $G$ has a star edge-coloring from $L$. Dvo?ák et al. (2013) asked whether the list star chromatic index of every subcubic graph is at most 7. In Kerdjoudj et al. (2017) we proved that it is at most 8. In this paper we consider graphs with any maximum degree, we proved that if the maximum average degree of a graph $G$ is less than $\frac{14}{5}$ (resp. 3), then $c{h}_s^{\prime }\left(G\right)\le 2\Delta \left(G\right)+2$ (resp. $c{h}_s^{\prime }\left(G\right)\le 2\Delta \left(G\right)+3$).     

Vector subspaces of finite fields and star operations on pseudo-valuation domains

Given an extension of finite fields $F\subseteq L$, we study the number of the equivalence classes of F-vector subspaces of L modulo multiplication by elements of L, obtaining an exact formula and some bounds. We then apply the results obtained to the study of the set of F-star operations on L, which correspond to star operations on a pseudo-valuation domain R.