搜索结果: 1-15 共查到“知识库 组合数学 graphs”相关记录46条 . 查询时间(0.122 秒)
We show that for integers k > 1 and n > 2, the diameter of the Cayley graph of SLn(Z/kZ) with respect to a standard two-element generating set, is at most a constant times n2 ln k. This answers a ques...
Combined degree and connectivity conditions for H-linked graphs
Combined degree connectivity conditions H-linked graphs Combinatorics
2012/6/27
For a given multigraph H, a graph G is H-linked, if |G| \geq |H| and for every injective map {\tau}: V (H) \rightarrow V (G), we can find internally disjoint paths in G, such that every edge from uv i...
Constructing graphs with no immersion of large complete graphs
Graph immersion minimum degree chromatic number edgeconnectivity Hajos Conjecture Hadwiger Conjecture graph minor
2012/6/29
In 1989, Lescure and Meyniel proved, for $d=5, 6$, that every $d$-chromatic graph contains an immersion of $K_d$, and in 2003 Abu-Khzam and Langston conjectured that this holds for all $d$. In 2010, D...
We prove that every claw-free graph $G$ that doesn't contain a clique on $\Delta(G) \geq 9$ vertices can be $\Delta(G) - 1$ colored.
Determination of Integral Cayley Graphs on Finite Abelian Groups
abelian group character cayley graph integral graph
2012/6/21
A graph is integral means that all its eigenvalues are integers. In this note, we determine all the integral Cayley graphs on finite abelian groups. Moreover, we calculate the the number of integral C...
Eigenvalue interlacing and weight parameters of graphs
Eigenvalue interlacing weight parameters of graphs Combinatorics
2012/6/15
Eigenvalue interlacing is a versatile technique for deriving results in algebraic combinatorics. In particular, it has been successfully used for proving a number of results about the relation between...
A set $W\subseteq V(G)$ is called a resolving set, if for each two distinct vertices $u,v\in V(G)$ there exists $w\in W$ such that $d(u,w)\neq d(v,w)$, where $d(x,y)$ is the distance between the verti...
The p-Domination Number of Complete Multipartite Graphs
p-domination set p-domination number complete multipartite graph
2012/5/9
Let $G=(V,E)$ be a graph and $p$ a positive integer. A subset $S\subseteq V$ is called a $p$-dominating set of $G$ if every vertex not in $S$ has at least $p$ neighbors in $S$. The $p$-domination numb...
Odd-order Cayley graphs with commutator subgroup of order pq are hamiltonian
Cayley graph hamiltonian cycle commutator subgroup
2012/5/9
We show that if G is a nontrivial, finite group of odd order, whose commutator subgroup [G,G] is cyclic of order p^m q^n, where p and q are prime, then every connected Cayley graph on G has a hamilton...
A connection between the bipartite complements of line graphs and the line graphs with two positive eigenvalues
line graphs graph spectra complements Courant-Weyl inequalities
2012/4/16
In 1974 Cvetkovi\'c and Simi\'c showed which graphs $G$ are the bipartite complements of line graphs. In 2002 Borovi\'canin showed which line graphs $L(H)$ have third largest eigenvalue $\lambda_3\leq...
Counting independent sets of a fixed size in graphs with a given minimum degree
graphs given minimum degree independent sets Combinatorics
2012/4/16
Galvin showed that for all fixed $\delta$ and sufficiently large $n$, the $n$-vertex graph with minimum degree $\delta$ that admits the most independent sets is the complete bipartite graph $K_{\delta...
Coloring, location and domination of corona graphs
Coloring domination location Roman domination corona graphs
2012/4/18
A vertex coloring of a graph $G$ is an assignment of colors to the vertices of $G$ such that every two adjacent vertices of $G$ have different colors. A coloring related property of a graphs is also a...
Domination related parameters in rooted product graphs
Domination location domination related parameters rooted product graphs
2012/4/18
A set $S$ of vertices of a graph $G$ is a dominating set in $G$ if every vertex outside of $S$ is adjacent to at least one vertex belonging to $S$. A domination parameter of $G$ is related to those se...
Generalized Measures of Edge Fault Tolerance in (n,k)-star Graphs
Combinatorics fault-tolerant analysis (n, k)-star graphs edge-connectivity h-super edge-connectivity
2012/4/18
This paper considers a kind of generalized measure $\lambda_s^{(h)}$ of fault tolerance in the $(n,k)$-star graph $S_{n,k}$ for $2\leqslant k \leqslant n-1$ and $0\leqslant h \leqslant n-k$, and deter...
Note on group distance magic graphs $G[C_4]$
distance magic labeling magic constant sigma labeling graph labeling Abelian group
2012/4/23
A \emph{group distance magic labeling} or a $\gr$-distance magic labeling of a graph $G(V,E)$ with $|V | = n$ is an injection $f$ from $V$ to an Abelian group $\gr$ of order $n$ such that the weight $...